[clangd] [C++20] [Modules] Support C++20 modules for clangd

[ChuanqiXu]

Summary

Try to address https://github.com/clangd/clangd/issues/1293. See the link for some design ideas.

What this patch does:

• Offers an option "-experimental-modules-support" for the new feature. So that no matter how bad this is, it wouldn't affect current users. Following off the page, we'll assume the option is enabled.
• When we load a compilation database, we will try to scan every TU recorded in the compilation database by the same process of clang-scan-deps to get the modules related files. For these modules related files, we will build a modules dependency graph based on the scanning results.
• Every time we update a file, all the affected files (e.g., we changed a header file) will be re-scanned. This is necessary since we don't know if the change will introduce modules related things. And we will update the modules graph.
• When we want to build a file, we will try to see if all the BMIs of the its dependencies are already built (third party modules are not included), if yes, go ahead to compile it. If not, we will wait for the modules manager to try to build all the dependent BMIs. No matter if the building is success or not, we will be resumed. Note that this implies that the BMIs are built lazily.
• When we compile a file, all the options (-fmodule-file=<module-name>=<module-path>) to specify the position of BMIs will be dropped. And the new modules global compilation database will insert a new search path to the BMIs built by clangd itself. So that we're not version locked with the compiler the user uses and we won't affect user's build.

Missing functionalities

The major missing functionality is that when we update a module unit, its users won't update automatically. For example,

// b.cppm
export module b;
export int bb = 43;

// a.cpp
import b;
int aa = bb;

After initialization, we will see the value of bb in a.cpp is correctly 43 in the code intelligence. But if we change the value of bb into 44 in b.cppm, the value of bb displayed in a.cpp is still 43. We can get the newest result by inserting and deleting an empty line to a.cpp and save it. (Any change should work too.)

The reason why I don't address this in the patch is that the patch itself is already big now. The larger it is, the harder it is to review it. Also I think it is usable in some level. So let's try to address this in later patches.

Other problems

The major problem I see now is that we can't handle third party modules. Third party modules refer to the modules whose source codes are not in current project. The users are still able to see the hint from clangd if the BMI of the third party modules are built ahead of time. I think this is true for a lot use cases. But this breaks our goal to not be locked by the same version compiler.

I think we can only solve the issue after SG15 solves it. I know SG15 is discussing how to let the modules communicate across libraries boundary. And it is not wise to invent wheels agains SG15. So let's wait for that.

Unable to make the clangd built BMI persist now

In the above link, @nridge requires to persist the clangd built BMIs so that we can reuse the BMIs across the invocation of clangd. This is not addressed in the patch. One reason is the same with above one. The current patch is already large. And I find that it is not trivial to do this. Since we need to check the consistency of the built BMI with the source codes. I know clang has similar functionalities but I feel we may need some code to adapt that. So I choose to not implement it in the first step.

Performance

I tested this with a modularized library: https://github.com/alibaba/async_simple/tree/CXX20Modules. This library has 3 modules (async_simple, std and asio) and 65 module units. (Note that a module consists of multiple module units). Both std module and asio module have 100k+ lines of code (maybe more, I didn't count). And async_simple itself has 8k lines of code. This is the scale of the project.

I opened a file in the end of the dependency chain and restart the clangd server, the log shows that it takes 10s to get things ready.

hmmm not a good number actually. But I found the major reason is that the speed to built the BMIs is too slow. And the major potential improvements should live in the compiler side. The compiler should offer an option to build BMIs lightly. I don't feel we can do a lot in the clangd side.

I think currently the performance issues should mainly be related to the number module units and the lines of code in the module units. That said, it doesn't matter if we have a big project but there is no or small scaled module units.

Plans

This is clearly not so good. But I feel it is basically workable. A little bit awkward to get this in the end of the release circle. But I still want to try to land this in clang17 as it is an important features to modules users.

If we can land this, I plan to implement the light mode in clang first and implement the persist BMI feature then.

[sammccall]

Thanks for putting this together, I'm going to study it carefully and try it out!

That said, there are two large issues that I think should be addressed in the design (though not necessarily *implemented* now).
I'll be upfront: these are things without which $EMPLOYER will not be able to use this at all.
Since there isn't really room for multiple modules implementations in clangd, I'd like to make sure these fit into the design, or can be bolted on.

In the past, we've been reasonably successful at finding extension points that let clangd scale to unreasonable codebase sizes, while doing the right thing for smaller projects too. (Index, build system integration, VFS support, etc). To quote from the bug:

you will need an alternative for them (luckily most of them already are willing to invest in custom tooling), but scanning all project files should still be fine for the vast majority of clangd users

For historical context: clangd was that custom tooling designed to scale to huge monorepos. Google needs to continue to pay the cost of such support for new features, and we're trying to make that happen real soon now...

---

support for clang header modules

Google has a large deployment of clangd, serving a codebase that builds significant parts as clang header modules for performance reasons. There is no near-term plan of adopting C++20 modules (multiple reasons, which I probably can't represent well).
We've been disabling header modules for clangd & other tools for a long time. But it's come to a head, and we expect to get someone working on enabling modules in clangd in ~2 months.
As I understand it, Meta are in a similar situation (though their solution is to version-lock clangd with the toolchain, keep modules enabled, and accept that some things are broken).

Our specific build system setup is that all module-build actions and inputs explicit (-fmodule-file=, -fmodule-map-file=). The build system will not produce usable PCMs due to version skew.
I know that Meta folks *would* like to make use of available PCMs from the build system.

---

support for large projects

We have multiple codebases large enough that touching every file to discover dependencies isn't feasible.
The largest internal one had 2B LOC 7 years ago, and is now much larger. But even Chrome for example has 20M. Such projects are prone to adopt modules (in some form) for build scalability.
Apart from the concrete scanning of deps, keeping the full project module graph in memory won't always be possible. (It's a perfectly reasonable default implementation though).

[sammccall]

(Sorry, hit send too soon)

I suspect the answer for header modules is that we can study this patch and understand what the equivalents of graph nodes/deps/names/scanning look like for explicit header modules, and understand that we'll be able to abstractify some names and add some levels of indirection and it'll all work out.

For large project support, I suspect a bit more thought is needed.
We'll need some abstraction layer (like CompilationDatabase is to compile_commands.json) that exposes enough data to run the algorithms we need, without exposing so much that you have to hold the whole graph in memory. It could be backed by in-memory depscan results, or a build-system artifact, or a live query of the build system.
For "every time we update a file, all the affected files (e.g., we changed a header file) will be re-scanned" - we need a way to express this more abstractly than "re-scanned", and more narrowly than "all the affected files" - at least it needs to be limited to all the files that could themselves affect any open file.

(Going to dig into the design now and come back with more thoughts)

[nridge]

The major problem I see now is that we can't handle third party modules. Third party modules refer to the modules whose source codes are not in current project. The users are still able to see the hint from clangd if the BMI of the third party modules are built ahead of time. I think this is true for a lot use cases. But this breaks our goal to not be locked by the same version compiler.

I think we can only solve the issue after SG15 solves it. I know SG15 is discussing how to let the modules communicate across libraries boundary. And it is not wise to invent wheels agains SG15. So let's wait for that.

For context, SG15 is the ISO C++ standards committee's Tooling Study Group. One proposal being looked at that may be relevant here is P2581 - Specifying the Interoperability of Built Module Interface Files.

[ChuanqiXu]

That said, there are two large issues that I think should be addressed in the design (though not necessarily *implemented* now).

Yeah, totally agreed. Design is pretty important especially in open source softwares. I'm pretty open to any ideas.

---

support for clang header modules

Google has a large deployment of clangd, serving a codebase that builds significant parts as clang header modules for performance reasons. There is no near-term plan of adopting C++20 modules (multiple reasons, which I probably can't represent well).
We've been disabling header modules for clangd & other tools for a long time. But it's come to a head, and we expect to get someone working on enabling modules in clangd in ~2 months.
As I understand it, Meta are in a similar situation (though their solution is to version-lock clangd with the toolchain, keep modules enabled, and accept that some things are broken).

I suspect the answer for header modules is that we can study this patch and understand what the equivalents of graph nodes/deps/names/scanning look like for explicit header modules, and understand that we'll be able to abstractify some names and add some levels of indirection and it'll all work out.

Yeah. On the one hand, I always think that named modules are far different from header modules (including clang header modules and header units) for tools. Since for tools, it makes sense to fallback to traditional inclusion when they saw header units or header modules. For example,
for clang header modules, IIUC, clangd can work if we rewrite the compile commands to strip a lot of clang header modules related options. And we reuse the rewrite process in the patch. (I know there are some exceptions due to macros). On the other hand, I'm curious about how do you handle/model clang explicit header modules with compilation database? I didn't look about this. Is the headers an entry in the compilation database? And if is it possible for one header to have multiple BMIs? Such problems look not easy to handle so I prefer to fallback it to inclusions.

Another point here to make clangd to treat header modules as headers is that the process of building BMI is not cheap. Even if we developed a mode which can create BMI lightly, it is still not free. So I think it is better to treat header modules as headers for perspective of performance too.

Our specific build system setup is that all module-build actions and inputs explicit (-fmodule-file=, -fmodule-map-file=). The build system will not produce usable PCMs due to version skew.
I know that Meta folks *would* like to make use of available PCMs from the build system.

Also it looks like to me the Meta's method are not a solution we want. This looks basically what I want for named modules half a year ago. Basically I did nothing and just tried to let clangd fallback to clang to handle everything.

---

support for large projects

Apart from the concrete scanning of deps, keeping the full project module graph in memory won't always be possible. (It's a perfectly reasonable default implementation though).

We'll need some abstraction layer (like CompilationDatabase is to compile_commands.json) that exposes enough data to run the algorithms we need, without exposing so much that you have to hold the whole graph in memory. It could be backed by in-memory depscan results, or a build-system artifact, or a live query of the build system.

Yeah, I agree the performance is a key point. In the current design, the ModulesDependencyGraph is only visible to ModulesManager so I feel we left the space for further optimization while I don't have concrete ideas. The current patch only left 5 interfaces for outer users (currently only TUScheduler) (the interfaces: UpdateNode(PathRef), isReadyToCompile(PathRef), HasInvalidDependencies(PathRef), addCallbackAfterReady(PathRef, std::function<void()>) and GenerateModuleInterfacesFor(PathRef)), which didn't leak any special data to outer users. So I feel while it is OK to adopt ideas to enhance the scaling ability, it is OK to forward now since we've left the space for further optimization. (premature optimization is the root of all evil :) )

For "every time we update a file, all the affected files (e.g., we changed a header file) will be re-scanned" - we need a way to express this more abstractly than "re-scanned", and more narrowly than "all the affected files" - at least it needs to be limited to all the files that could themselves affect any open file.

Yeah, actually now this patch doesn't make it explicitly. Now we achieve this implicitly by making TUScheduler::update (which will be called every time the TU changes) to call ModulesManager::UpdateNode(PathRef). What I want to do is to let ModulesManager::UpdateNode(PathRef Node) to call TUScheduler::update for the users of Node.

So here "re-scanned" means to call TUScheduler::update. And "all the affected files" is not reflected in the patch actually. Do you have suggestions to improve this or do you feel it is OK to make it implicitly as now?

[Destroyerrrocket]

clang-tools-extra/clangd/ModulesManager.cpp

414–415

This is a bug; The second move is invalid. You could make a copy

[ChuanqiXu]

Address comments.

clang-tools-extra/clangd/ModulesManager.cpp

414–415

Done. Thanks for looking this. I changed it with a new signature for the callbacks with a bool argument.

[Destroyerrrocket]

clang-tools-extra/clangd/ModulesManager.cpp

414–415

No problem! I'd love to help :)

[ChuanqiXu]

@sammccall @nridge gentle ping~

[ChuanqiXu]

@sammccall @nridge gentle ping~

[nridge]

I'm sorry, I feel like I don't have a good enough level of insight into the requirements to usefully critique this patch, nor the bandwidth to take a detailed look through the implementation right now.

I think it's best for me to resign as reviewer for the time being, and leave the review in Sam's capable hands.

Sam, I hope this is ok; if you'd like a second opinion on any particular point, or a second pair of eyes on the implementation, please feel free to re-add me and I will do my best to make time to weigh in.

[ChuanqiXu]

@sammccall gentle ping~

[ChuanqiXu]

@sammccall gentle ping

[ilya-biryukov]

Hi @ChuanqiXu,

Sam is on vacation now, but we are in the same team and I am responding on behalf of the team.

First, sorry for not getting to this review earlier.
The change is quite big, and, as Sam mentioned, we want to make sure this scales to our (unreasonable) project sizes and supports for header modules.
That is to say, we feel that the stakes are high for getting it right.

In order to move forward with this change, we need to do some homework to figure out the longer-term strategy for modules in Clangd.
We plan to come back with answers, but it may take a few months because planning this urgently is tough.
I do want to stress that we want to get modules in Clangd right, plan to work on it.

Sorry for these delays and confusion.

[ChuanqiXu]

Got it. Being patience is not bad and it is good enough to know that we are moving forward : )

[ChuanqiXu]

BTW, I have a question about supporting header modules (including clang header modules and C++20 header units) in static analysing tools (including clangd), "why can't we fallback to include the corresponding headers simply?". So I still feel it is not a problem to support header modules in static tools. Since I feel the semantics of header modules is almost transparent to other tools.

[ilya-biryukov]

In D153114#4569591, @ChuanqiXu wrote:

BTW, I have a question about supporting header modules (including clang header modules and C++20 header units) in static analysing tools (including clangd), "why can't we fallback to include the corresponding headers simply?". So I still feel it is not a problem to support header modules in static tools. Since I feel the semantics of header modules is almost transparent to other tools.

We could and it mostly works. In fact, this is what we do internally at Google at build system level since our source tools don't support header modules, but the build does support them.
There are problems with this approach, though:

• Modules provide build time improvement that add up if they are widely used in the codebase. This leads to source tools being much slower than builds. This results in slowness and timeouts when source tools are used.
• There are still incompatibilities between header modules and preprocessor and we occasionally get code that builds, but source tools don't work on it.

I think we should be open to special-casing the header modules if they turn out to be hard to support compared to C++20 Modules.
However, my intuition is that that would not be the case and the major problems are actually quite similar between the two (versioning of PCMs we consume, when PCMs need to be rebuilt, etc) and we get header modules almost for free if we solve those problem for C++20 Modules.
But we do want to make sure we don't miss anything important for header modules in the design phase as that's actually something used by Google today and it would be valuable to solve the aforementioned problems.

[ChuanqiXu]

Got it. The explanation makes sense. A well designed and scaling solution is what I (and probably every one) want.

Then from the expectation, the difference between supporting header modules and C++20 named modules from the user side may be:

• For supporting header modules in clangd, it is mainly a speed issue and some corner cases.
• For supporting C++20 named modules in clangd, it will be pretty hard for users to use named modules in practice.

In another word, it may not be super bad for not supporting header modules in clangd. But it is super bad for named modules. So I am wondering if we can have an expectation for the time points to support named modules (even only experimentally) in clangd. For example, may it be a reasonable expectation that we can have named modules support in clangd in clang18? Clang18 will be released in the first week of March 2024. So that's still roughly 7 months away from now. I guess the time span may be sufficient. How do you feel about this? And if we have consensus on that, then we will need to move forward from the patch if we don't have solution in December at least. Since it takes time to review and experiment this further.

BTW, I don't mind someone else to take this job away completely as long as we can get the support in time. Since I am not a clangd developer : )

[ilya-biryukov]

In D153114#4571703, @ChuanqiXu wrote:

For example, may it be a reasonable expectation that we can have named modules support in clangd in clang18? Clang18 will be released in the first week of March 2024. So that's still roughly 7 months away from now. I guess the time span may be sufficient. How do you feel about this? And if we have consensus on that, then we will need to move forward from the patch if we don't have solution in December at least. Since it takes time to review and experiment this further.

BTW, I don't mind someone else to take this job away completely as long as we can get the support in time. Since I am not a clangd developer : )

Setting some deadlines totally makes sense and Clang 18 release looks like a very reasonable target.
Give us a few days to see if we can set this up. I hope to be back with concrete commitments by the end of this week or early next week.

[sammccall]

Sorry for the long radio silence here. There's a lot to chew on, and I put it off too long. Thanks for your patience!

I agree we should get experimental modules support landed in some form on the LLVM 18 timeline.
It's fine if this doesn't have extension points for large projects, or for header modules, and if it'll take some refactoring later to get there. Still, I think we should consider them in the architecture (partly because a second impl helps reason about interfaces).

I do think it's important we play nicely with the rest of clangd infrastructure: things like threading/context, VFS clean-ness, ability to easily write gtests for modules-enabled ASTs.

This initial pass probably mostly comes across as a list of complaints... I'd like to be more constructive & provide ideas, but this is long already so I'll follow up with that.

I've tried to limit to mostly high-level comments (or at least details that require a bit of thought!)
A couple more that don't fit anywhere:

---

Indexing

Much of clangd's functionality relies on having an up-to-date index of the transitively included headers (and now, modules).
While we're more relaxed about having a full-project index, this preamble index really is essential.

It's infeasible to build this index from the PCM files themselves: this means fully deserializing them and is too expensive (we tried this with PCH).
Traditionally we indexed the preamble the ASTContext before serializing the PCH, though recently this is optionally async.
(You can see this in onPreambleAST in ClangdServer.cpp and trace from there.)

I think indexing can be left out of this initial patch, but we should work out where/how it fits and leave a comment!

---

Scope and incremental development

There are a lot of moving pieces to this. That's useful to understand how they all fit together (which is necessary whether they're in the same patch or not).
However it makes difficult to review, and to drive a review to a conclusion. I think we should change the scope of the initial patch to establish a small subset that works and we understand well:

Don't attempt any cross-file or cross-version coordination: i.e. don't try to reuse BMIs between different files, don't try to reuse BMIs between (preamble) reparses of the same file, don't try to persist the module graph. Instead, when building a preamble, synchronously scan for the module graph, build the required PCMs on the single preamble thread with filenames private to that preamble, and then proceed to build the preamble.

Obviously this no longer provides any performance benefits from modules! But it gets us to a modules-based build that works, and these aspects can be added on top in a relatively clear way.
It avoids a lot of tricky problems:

• scheduling
• (lack of) transactionality of reads/writes from the module graph
• the possibility of BMI version conflicts
• various events that can invalidate the module graph
• rebuilding of BMIs when source files change (the current patch deliberately doesn't do this to keep the scope down, but that means the result is both complex and incorrect, which is a difficult situation to get out of)

I think this also encourages us to unbundle some of the "ModulesManager"'s responsibilities and will lead to a better API there.

Do consider the lifecycle/namespacing of BMI files on disk

While we may eventually want to reuse BMIs between (sequential or concurrent) clangd instances, this is complicated and IMO won't happen soon (needs to deal with source versioning, I believe).

Therefore for now we should treat the BMIs as transient, conceptually like in-memory objects. In practice we want to store them on disk for size reasons, but these should have transient tempfile names that will never conflict, should be deleted on shutdown etc. (It's fine to do basic delete-on-destruction and leave crash-handling etc out for now).

clang-tools-extra/clangd/ModulesManager.cpp

51

the docs suggest this tool is going to spawn threads.

clangd needs to retain control of thread spawning, e.g. to ensure clangd::Context is propagated (required for config, tracing and others), thread priorities are set appropriately etc.

56

It looks like this performs IO for the dependency scanning.
The files may not be on a real filesystem, IO on source files should go through the configured VFS (see ThreadsafeFS from which you can obtain a concrete FS for the desired operation).

57

it seems like the library under some circumstances expects to be able to write output to physical disk, and choose the path to do so (MakeformatOutputPath?)

What purpose does this serve here, and is it possible to avoid it?

While potentially it's OK to write to a temporary directory, we need to ensure concurrent clangd instances don't conflict, the files get eventually cleaned up after crashes, we're not writing too much in environments without physical disks etc.

107

note that clangd invocations are not necessarily sequential, there may be multiple clangd instances operating on the same codebase at the same time.

So we either need to ensure this store can be shared across instances without races, or treat it as transient (separate dir for each clangd process, clean up on shutdown and on crash)

321

This seems to be the only place that BMI path is cleared, which will cause the BMI to be rebuilt next time it is needed, correct?

We need to rebuild the BMI every time the content of a module has changed, though: we need the exposed APIs to be up-to-date (and the SourceLocations etc).
Nothing seems to be doing this, so it seems we're going to keep using stale copies of headers forever.

(CDB.watch isn't anywhere close to sufficient here: it's best effort, it's async, and it only tells when compile flags changed, not the file content).

526

this doesn't seem like a valid thing to assert here, or anywhere

we don't hold the lock at this point, so the graph may have changed since whatever precondition the caller established.
In particular, it may now have invalid dependencies.

(This seems like a manifestation of the idea that we need some idea of snapshots in the graph and versioning of the BMIs we create)

562

How do we handle the following scenario?

1. we get a call to GenerateModuleInterfacesFor("a.cpp"), where a.cpp => X => Z
2. we recursively build Z.pcm#1 and X.pcm and we're just about to return...
3. now somehow we find out that Z changed (and clear its BMI path)
4. and we get a call to GenerateModuleInferfacesFor("b.cpp"), where b.cpp => Y => Z
5. now we recursively build Z.pcm#2 and Y.pcm
6. finally the original call to GenerateModuleInterfacesFor("a.cpp") returns

---

• In this end state, we have modules for X and Z, but they can't be used together: X.pcm was build against Z.pcm#1 but we have Z.pcm#2. So a.cpp produces a mysterious PCM-related error.
• If we solve this by invalidating X's BMI path when we invalidate Z's, then we just end up with a.cpp failing to compile with a missing PCM.
• if we solve this by having GenerateModuleInterfacesFor basically loop until everything is up to date, then we stop guaranteeing forward progress when the system is busy, and *still* race because things can get out of date as soon as we return

I believe solving this class of problem probably means explicitly accounting for versions, and keeping refcounted versioned PCMs that are pinned while we're using them.

clang-tools-extra/clangd/ModulesManager.h

29

these details seem unused outside the cpp file (and untested), so should be in the cpp file - this would make it easier to understand which part of this file is the interface

57

Concretely, for the implementation where we scan the whole project up front, the data structure here can be an in-memory graph.

However rather than having fine-grained methods to query attributes of the graph, I think we should work out which high-level/coarse-grained queries we should support.

The current API leads to locking/unlocking the graph many separate times to obtain/update different information, and it's very difficult to reason about whether the behavior is correct if the graph changes in between. Coarse-grained single queries can be made atomic and queried once.

This will also result in an interface much more suitable for other implementation strategies, such as querying a build system that understands modules. (We will need to have this available as an extension point, as scanning the whole project does not scale to larger codebases)

117

I'd like to choose a different name than "third-party", which often (at least inside LLVM and inside google) refers to "vendored" libraries where we *do* always have headers and often build entirely from source.

Moreover, I think at least initially we should not support these in any way, and ensure we produce an error for the import statement.
In the majority and baseline case, the compiler may not be clang, and is probably at least a different version with incompatible BMI files.
(There may eventually be cases where we want to try making use of externally provided BMIs, but this is mostly orgthogonal to third-party-ness, I tihnk)

This means the signature here shouldn't need to call out third-party modules as special - these should be modeled the same way as if there was a dependency we couldn't build a BMI for for some other reason.

205

Generally "ModulesManager" is worryingly vague as a set of responsibilities, and this class looks like it does too much: provides threadsafe access to the module graph, performs actual scanning and BMI-building logic, and also acts as the scheduler.

I think we'll need to separate these concerns out into separate APIs, but it's probably best if we think about this later after understanding how to address more concrete questions.

clang-tools-extra/clangd/TUScheduler.cpp

867

This call to IsReadyToCompile seems to have a logic race:

• we've previously queried the module manager as part of preparing the compile command
• now we're querying it again based on the filename
• what happens if the graph has changed significantly in the meantime?

871

making ModulesCV a member etc, exposing waitForModulesBuilt etc suggests we're going to wait on this for multiple threads. But I don't see that here.

If this is merely local, can we have:

Notification N;
addCallbackAfterReady([] { N.Notify(); });
N.wait();

or even just give ModuleMgr a blocking API?

874

we need to be able to handle shutdown while waiting for modules

874

here the ASTWorker is apparently blocking on all the modules being up-to-date (though the impl doesn't seem to actually achieve up-to-date-ness, I assume that's the intent).

This creates a big performance cliff where modifying a low-level header causes all features to stop working until everything that transitively depends on it is rebuilt. We used to have this cliff with preambles, though extensive effort we've eliminated it through the use of a separate preamble thread, tolerance for stale preambles, preamble patching etc.

I think the fix is roughly:

• we assume imports are in the preamble (I think the language guarantees this idea works, though clang's actual preamble implementation may or may not support this right now)
• the preambleworker should be blocking on modules being ready, not the astworker. This (usually) takes it off the critical interactive path
• typically the preamble will now be a fairly small thing that's mostly references to PCMs
• we need to ensure the PCMs survive (and aren't overwritten by newer versions) for as long as the preamble is alive and used. Some sort of owner class stored in PreambleData can achieve this.

(one day it may be possible to eliminate the use of preamble altogether in favor of some modules-based solution, with header modules inferred for non-modularized code. But obviously we can't do that until this is non-experimental, so the preamble is the best place for modules to live for now)

clang-tools-extra/clangd/test/modules.test

2

A smoke lit test is great, it's not realistic to achieve good test coverage of features this way though (and generally we don't try).

We'll need to work out how to get TestTU-based tests to work with modular builds.

[ChuanqiXu]

@sammccall Hi, Sam. Thanks for your high-quality comments! It is valuable. All the low-level inline comments are helpful. But I didn't reply them for the suggested direction in the higher level comments.

I'll repeat your suggestion in my mind again to avoid any misunderstandings:

While we should leave the space for future development, we should do the following thing in the initial patch:

Don't attempt any cross-file or cross-version coordination: i.e. don't try to reuse BMIs between different files, don't try to reuse BMIs between (preamble) reparses of the same file, don't try to persist the module graph. Instead, when building a preamble, synchronously scan for the module graph, build the required PCMs on the single preamble thread with filenames private to that preamble, and then proceed to build the preamble.

Do I understand right? If I understand correctly, I fully agree with the direction. We can go slowly, as long as we keep moving forward.

Then I'd like to leave the patch as-is for referencing and create new patches following the suggestion.

[sammccall]

In D153114#4602414, @ChuanqiXu wrote:

Don't attempt any cross-file or cross-version coordination: i.e. don't try to reuse BMIs between different files, don't try to reuse BMIs between (preamble) reparses of the same file, don't try to persist the module graph. Instead, when building a preamble, synchronously scan for the module graph, build the required PCMs on the single preamble thread with filenames private to that preamble, and then proceed to build the preamble.

Do I understand right? If I understand correctly, I fully agree with the direction. We can go slowly, as long as we keep moving forward.

Then I'd like to leave the patch as-is for referencing and create new patches following the suggestion.

Yes, that's the suggestion, and that plan makes sense to me, thanks!

I did some more thinking about this (having a concrete implementation helps a lot!) and had a couple more thoughts.
At some point we should write down a design somewhere, need to strike a balance between doing it early enough to be useful but late enough that we've understood!

Dep scanning - roles

IIUC we do this for two reasons:

• to identify what module names we must have PCMs for in order to build a given TU (either an open file, or a module we're building as PCM)
• to build a database mapping module name => filename, which we compose with the CDB to know how to build a PCM for a given module name

I think it would be good to clearly separate these. The latter is simpler, more performance-critical, async, and is probably not used at all if the build system can tell us this mapping.
The latter is more complex, and will always be needed synchronously for the mainfile regardless of the build system.

Dep scanning - implementation

The dep scanner seems to work by getting the compile command and running the preprocessor. This is fairly heavyweight, and I can't see anywhere it's going into single-file mode - is it really reading all #included headers? This is certainly not workable for reparses of the mainfile (when no headers have changed).

It seems unneccesary: the standard seems to go to some lengths to ensure that we (almost) only need to lex the top-level file:

• module and import decls can't be produced by macros (seems to be the effect of the pp-module directive etc)
• module and import decls can't be #included (definition of module-file and [cpp.import] rules)

The wrinkle I see is that some PP usage is possible: the module name can be produced by a macro, and imports can be #ifdefd. I think the former is very unlikely (like #include MACRO_NAME) and we can not support it, and the latter will just result in us overestimating the deps, which seems OK.
You have more context here though, and maybe I'm misreading the restrictions placed by the standard. Today clang doesn't seem to enforce most of these sort of restrictions, which is probably worth fixing if they're real.

(This doesn't apply to header modules: it's perfectly possible to include a textual header which includes a modular header, and it's impossible to know without actually preprocessing. This divergence is nasty, but I don't think we should pessimize standard modules for it).

Interaction with preamble

At a high level, import decls should be processed with the preamble: they should change infrequently, rebuilding modules is expensive, coarse-grained work, we want to make the same policy decisions on whether to use stale PCMs or block on fresh ones etc.
However they don't appear in a prefix of the file, and this is pretty important to how the preamble action works, so exactly in what sense are they part of the preamble?

I believe the best answer is:

• "preamble" is really a set of required artifacts + conditions to check for validity
• import foo in a file means foo.pcm is a required artifact, not that preamble.pcm contains an ImportDecl

So given this code:

module;
#include <x>
module foo;
import dep1;
module :private;
import dep2;

The "preamble region" should end after #include <x> and preamble.pcm should contain the AST & PP state up to that point.
Meanwhile dep1.pcm and dep2.pcm are separate PCM files that will be loaded on each parse.
For a preamble to be usable at all, we need to have built preamble.pcm, dep1.pcm, dep2.pcm.
For a preamble to be up-to-date, the preamble region + set of imported modules must be unchanged, the preamble.pcm must be up to date with respect to its sources, and the module PCMs must be up-to-date with respect to their sources. (unclear exactly how to implement the latter, may need to add extra tracking)

(When building this module as a PCM we may not want to treat dep2 as a dependency or parse the private fragment... but this is not relevant to preambles as we won't be using a preamble for this anyway)

[nridge]

In D153114#4603579, @sammccall wrote:

Dep scanning - roles

IIUC we do this for two reasons:

• to identify what module names we must have PCMs for in order to build a given TU (either an open file, or a module we're building as PCM)
• to build a database mapping module name => filename, which we compose with the CDB to know how to build a PCM for a given module name

I think it would be good to clearly separate these. The latter is simpler, more performance-critical, async, and is probably not used at all if the build system can tell us this mapping.
The latter is more complex, and will always be needed synchronously for the mainfile regardless of the build system.

I think the second instance of "the latter" was meant to be "the former" :)

At a high level, import decls should be processed with the preamble: [...]
However they don't appear in a prefix of the file

This point is not obvious to me: do you mean that there are coding styles that place import statements further down in the file, after non-trivial declarations?

If not, what stops us from altering the definition of "preamble" to something like "everything before the first declaration which is not an import/module declaration"?

[sammccall]

In D153114#4604438, @nridge wrote:

In D153114#4603579, @sammccall wrote:

• to identify what module names we must have PCMs for in order to build a given TU (either an open file, or a module we're building as PCM)
• to build a database mapping module name => filename, which we compose with the CDB to know how to build a PCM for a given module name

I think it would be good to clearly separate these. The latter is simpler, more performance-critical, async, and is probably not used at all if the build system can tell us this mapping.
The latter is more complex, and will always be needed synchronously for the mainfile regardless of the build system.

I think the second instance of "the latter" was meant to be "the former" :)

Oops, yes!

At a high level, import decls should be processed with the preamble: [...]
However they don't appear in a prefix of the file

This point is not obvious to me: do you mean that there are coding styles that place import statements further down in the file, after non-trivial declarations?

Yes:

• inside a module unit, imports must appear directly underneath the module declaration, above non-trivial declarations
• but non-module TUs can place imports anywhere in the file (at TU scope)

If not, what stops us from altering the definition of "preamble" to something like "everything before the first declaration which is not an import/module declaration"?

We *have* to find and build *all* the PCMs that will be imported - unlike with the current preamble PCH, we can't give up on some of them and fall back to textual inclusion.

We could also have the preamble region cover the imports that happen to be at the top - i.e. the PCH would contain these ImportDecls. But I don't know that actually achieves anything meaningful over stopping the preamble before the imports. Either way, each time we use the preamble we'll have load the imported PCMs.

---

I just realized my ideas for simplifying the dep scanning may not work: as well as named modules we could also have imports of header units, which presumably means we need to at least build an include path and stat files on it to resolve a header unit name :-(

[ChuanqiXu]

In D153114#4603579, @sammccall wrote:

In D153114#4602414, @ChuanqiXu wrote:

Don't attempt any cross-file or cross-version coordination: i.e. don't try to reuse BMIs between different files, don't try to reuse BMIs between (preamble) reparses of the same file, don't try to persist the module graph. Instead, when building a preamble, synchronously scan for the module graph, build the required PCMs on the single preamble thread with filenames private to that preamble, and then proceed to build the preamble.

Do I understand right? If I understand correctly, I fully agree with the direction. We can go slowly, as long as we keep moving forward.

Then I'd like to leave the patch as-is for referencing and create new patches following the suggestion.

Yes, that's the suggestion, and that plan makes sense to me, thanks!

I did some more thinking about this (having a concrete implementation helps a lot!) and had a couple more thoughts.
At some point we should write down a design somewhere, need to strike a balance between doing it early enough to be useful but late enough that we've understood!

Yeah, then let's make the page into some design ideas discussing page.

Dep scanning - roles

IIUC we do this for two reasons:

• to identify what module names we must have PCMs for in order to build a given TU (either an open file, or a module we're building as PCM)
• to build a database mapping module name => filename, which we compose with the CDB to know how to build a PCM for a given module name

I think it would be good to clearly separate these. The latter is simpler, more performance-critical, async, and is probably not used at all if the build system can tell us this mapping.
The latter is more complex, and will always be needed synchronously for the mainfile regardless of the build system.

Yes, agreed.

Dep scanning - implementation

The dep scanner seems to work by getting the compile command and running the preprocessor. This is fairly heavyweight, and I can't see anywhere it's going into single-file mode - is it really reading all #included headers? This is certainly not workable for reparses of the mainfile (when no headers have changed).

It seems unneccesary: the standard seems to go to some lengths to ensure that we (almost) only need to lex the top-level file:

• module and import decls can't be produced by macros (seems to be the effect of the pp-module directive etc)
• module and import decls can't be #included (definition of module-file and [cpp.import] rules)

The wrinkle I see is that some PP usage is possible: the module name can be produced by a macro, and imports can be #ifdefd. I think the former is very unlikely (like #include MACRO_NAME) and we can not support it, and the latter will just result in us overestimating the deps, which seems OK.
You have more context here though, and maybe I'm misreading the restrictions placed by the standard. Today clang doesn't seem to enforce most of these sort of restrictions, which is probably worth fixing if they're real.

(This doesn't apply to header modules: it's perfectly possible to include a textual header which includes a modular header, and it's impossible to know without actually preprocessing. This divergence is nasty, but I don't think we should pessimize standard modules for it).

There are some problems due to the complexities of the standard...

The take away may be:

• module and import decls can't be produced by macros (seems to be the effect of the pp-module directive etc)
  • yes
• module and import decls can't be #included (definition of module-file and [cpp.import] rules)
  • the module declarations can't be #included.
  • but the import decls can be #included partially. See the discussion of https://github.com/llvm/llvm-project/issues/59688 for detail. The explanation is:
    • the wording(http://eel.is/c++draft/cpp.import#3) is "If a pp-import is produced by source file inclusion (including by the rewrite produced when a #include directive names an importable header) while processing the group of a module-file, the program is ill-formed."
    • and the definition of module-file (http://eel.is/c++draft/cpp.pre#nt:module-file) is pp-global-module-fragment pp-module group pp-private-module-fragment.
    • so the phrase the group of a module-file only refers to the group in the definition of module-file literally. We can't expand the grammar.
• the module name can be produced by a macro
  • yes
• imports can be #ifdefd.
  • yes. And this is a pretty important use-case for using modules in practice.

So possibly we have to look into the #includes when scanning.

Interaction with preamble

At a high level, import decls should be processed with the preamble: they should change infrequently, rebuilding modules is expensive, coarse-grained work, we want to make the same policy decisions on whether to use stale PCMs or block on fresh ones etc.
However they don't appear in a prefix of the file, and this is pretty important to how the preamble action works, so exactly in what sense are they part of the preamble?

I believe the best answer is:

• "preamble" is really a set of required artifacts + conditions to check for validity
• import foo in a file means foo.pcm is a required artifact, not that preamble.pcm contains an ImportDecl

So given this code:

module;
#include <x>
module foo;
import dep1;
module :private;
import dep2;

The "preamble region" should end after #include <x> and preamble.pcm should contain the AST & PP state up to that point.
Meanwhile dep1.pcm and dep2.pcm are separate PCM files that will be loaded on each parse.
For a preamble to be usable at all, we need to have built preamble.pcm, dep1.pcm, dep2.pcm.
For a preamble to be up-to-date, the preamble region + set of imported modules must be unchanged, the preamble.pcm must be up to date with respect to its sources, and the module PCMs must be up-to-date with respect to their sources. (unclear exactly how to implement the latter, may need to add extra tracking)

(When building this module as a PCM we may not want to treat dep2 as a dependency or parse the private fragment... but this is not relevant to preambles as we won't be using a preamble for this anyway)

Agreed basically. To make it clear, I think what you proposed may be to make clang::clangd::PreambleData contains the paths (or wrapped data structures) to dep1.pcm and dep2.pcm. And other parts of clangd should interact with the dep1.pcm or dep2.pcm with clang::clangd::PreambleData?

For a preamble to be up-to-date, the preamble region + set of imported modules must be unchanged, the preamble.pcm must be up to date with respect to its sources, and the module PCMs must be up-to-date with respect to their sources. (unclear exactly how to implement the latter, may need to add extra tracking)

For this issue, (and the related ABA issue you gave inline comments), my thought was that the code intelligence doesn't have to have super strict real time requirement with the compilation systems. I mean, in my real experience, it is not so bad to see out-of-date results from code intelligence than the results from compilation systems. (I know this may not be accepted.)

inside a module unit, imports must appear directly underneath the module declaration, above non-trivial declarations

Then this is not so correct. With the explanation in the same link above (https://github.com/llvm/llvm-project/issues/59688), the following example may be valid:

cpp
// a.cpp
export module a;

hpp
// b.hpp
import a;

cpp
// c.cpp
module;
#include <b.hpp>
export module c;

[ChuanqiXu]

@sammccall here is a question (or double check) about the intended initial version.

This is the requirement for the initial version:

Don't attempt any cross-file or cross-version coordination: i.e. don't try to reuse BMIs between different files, don't try to reuse BMIs between (preamble) reparses of the same file, don't try to persist the module graph. Instead, when building a preamble, synchronously scan for the module graph, build the required PCMs on the single preamble thread with filenames private to that preamble, and then proceed to build the preamble.

And all of us agree that it will be the job of the preamble to manage the module files in the end of the day. I just want to ask or double check that it might be OK to not related the module files with preamble in the initial version, right?

Since the definition (or description) of preamble is:

A preamble can be reused between multiple versions of the file until invalidated by a modification to a header, compile commands or modification to relevant part of the current file.

And it looks like it beyonds the scope of the our requirement of the initial patch.

[sammccall]

Aside: I've been doing some investigation into how modules+clangd could work in our huge monorepo (specifically bazel + distributed build cluster).
It looks feasible (with some serious effort) to get all BMI/index/etc data we need for transitive modules to be generated by a copy of clangd running in the distributed build system itself, and likely this will perform better than anything involving building in-process.
So it seems plausible to add a coarse-grained extension point for this, and assume that the "find-and-build-modules" part we're adding now doesn't have to scale to that size. (We'd still like it to scale to projects the size of Chromium, which is roughly 10x LLVM and our usual proxy for "large local project"). I think we can make some simplifying assumptions even beyond experimental stage:

• the module graph will fit in memory
• the compilation database will fit in memory
• the set of files in the project is enumerable
• reading all the source files in the project is possible: takes minutes but not hours

In D153114#4612843, @ChuanqiXu wrote:

@sammccall here is a question (or double check) about the intended initial version.

This is the requirement for the initial version:

Don't attempt any cross-file or cross-version coordination: i.e. don't try to reuse BMIs between different files, don't try to reuse BMIs between (preamble) reparses of the same file, don't try to persist the module graph. Instead, when building a preamble, synchronously scan for the module graph, build the required PCMs on the single preamble thread with filenames private to that preamble, and then proceed to build the preamble.

And all of us agree that it will be the job of the preamble to manage the module files in the end of the day. I just want to ask or double check that it might be OK to not related the module files with preamble in the initial version, right?

Since the definition (or description) of preamble is:

A preamble can be reused between multiple versions of the file until invalidated by a modification to a header, compile commands or modification to relevant part of the current file.

And it looks like it beyonds the scope of the our requirement of the initial patch.

On the one hand, if building modules in the AST works and is simpler, sure we can delay the "preamble optimization" for them.

But I don't really expect this is the case:

• as we've established, you can reach import statements inside the preamble region (#include a textual header that itself contains an import). So you need to build at least some of the required BMIs before building the preamble, doing it when parsing the main AST is not enough. (I believe the current version of the patch will just fail to parse some code in the preamble in this case).
• rebuilding BMIs with every preamble (not trying to reuse/cache/version them yet) will be pretty slow. But if we rebuild them every main-file reparse (i.e. every keystroke!) I think this is going to be intolerably slow to the point of not even being useful as a prototype.
• I only see two things that are really different between building during preamble vs building during AST, and neither are a lot of work:
  • invalidation: we need the preamble to be invalid if imports outside the preamble region have changed, or if the inputs of modules themselves have changed. But I think we can punt on all of this for now, and just not rebuild the preamble sometimes when we should. (Workaround: manually touch the preamble region after adding imports)
  • we need to attach the modules to PreambleData, rather than having them local to ParsedAST::build. But this really does not seem like much work at all - as we're not (yet) sharing modules through the filesystem, encapsulating the lifetime of a generated module in an object is something we should be doing right from the start anyway.
• given this, adding the code to ASTWorker and then moving it to PreambleWorker later seems like it doesn't save anything much over doing it right in the first place

[ChuanqiXu]

@sammccall @nridge while I am looking for the initial support for modules in clangd, I failed to find the mechanism to update files after I update a header file.

e.g., when I am opening the following file:

// a.cc
#include "a.h"
...

and there is a concurrent update to a.h. How can the ASTWorker of a.cc know such changes so that it can update the corresponding Preamble of a.cc?

In the comments of ClangdServer::reparseOpenFilesIfNeeded(), I see:

/ Requests a reparse of currently opened files using their latest source.
/ This will typically only rebuild if something other than the source has
/ changed (e.g. the CDB yields different flags, or files included in the
/ preamble have been modified).

So I thought this is what I want. However, I can't search the caller of reparseOpenFilesIfNeeded which semantics matches the behavior. The two callers of reparseOpenFilesIfNeeded I found are ClangdLSPServer::applyConfiguration() and ClangdLSPServer::onDocumentDidSave() and neither of them matches description files included in the preamble have been modified.

So I want to ask what's the behavior when I update a header and where is the corresponding code. Thanks.

[nridge]

In D153114#4630318, @ChuanqiXu wrote:

However, I can't search the caller of reparseOpenFilesIfNeeded which semantics matches the behavior. The two callers of reparseOpenFilesIfNeeded I found are ClangdLSPServer::applyConfiguration() and ClangdLSPServer::onDocumentDidSave() and neither of them matches description files included in the preamble have been modified.

So I want to ask what's the behavior when I update a header and where is the corresponding code. Thanks.

I'm afraid onDocumentDidSave() is all we have for now. It detects changes to the header when editing the header in the client (when the header is saved). I don't believe we have a mechanism for detecting changes to the header made in other ways.

If/when we want to add such a mechanism, I think the way to do it is using didChangeWatchedFiles (there is some discussion there about why LSP recommends servers delegate file-watching to the client rather than implementing file-watching in the server).

[ChuanqiXu]

In D153114#4630408, @nridge wrote:

In D153114#4630318, @ChuanqiXu wrote:

However, I can't search the caller of reparseOpenFilesIfNeeded which semantics matches the behavior. The two callers of reparseOpenFilesIfNeeded I found are ClangdLSPServer::applyConfiguration() and ClangdLSPServer::onDocumentDidSave() and neither of them matches description files included in the preamble have been modified.

So I want to ask what's the behavior when I update a header and where is the corresponding code. Thanks.

I'm afraid onDocumentDidSave() is all we have for now. It detects changes to the header when editing the header in the client (when the header is saved). I don't believe we have a mechanism for detecting changes to the header made in other ways.

IIUC, when we open a.cpp and b.h (there is no relationship between them), and we edit and save b.h, then the AST Worker of a.cpp will receive a request to update a.cpp. Did I understand correct? I imaged there may be an early exit point in the path of ASTWorker::update or PreambleThread::update if we detects the preamble doesn't change actually. But I failed to find it.

If/when we want to add such a mechanism, I think the way to do it is using didChangeWatchedFiles (there is some discussion there about why LSP recommends servers delegate file-watching to the client rather than implementing file-watching in the server).

Got it. And I am wondering the reason we didn't implement it may be that it is not so bad actually. Since a user generally won't open too many tabs. Do I understand right? And if it is the case, maybe we need to look at it in the future since it may be a concern with modules.

[sammccall]

In D153114#4630318, @ChuanqiXu wrote:

@sammccall @nridge while I am looking for the initial support for modules in clangd, I failed to find the mechanism to update files after I update a header file.

e.g., when I am opening the following file:

// a.cc
#include "a.h"
...

and there is a concurrent update to a.h. How can the ASTWorker of a.cc know such changes so that it can update the corresponding Preamble of a.cc?

The PrecompiledPreamble structure (defined in clang, not clangd) consists of a handle to the *.pch file, and also a list of filenames that it was built from. We can test whether it's out of date by stat()ing the input files (PrecompiledPreamble::CanReuse).

Once upon a time, clangd used this in a simple way: the ASTWorker always called [clangd::buildPreamble(inputs, old preamble)](https://github.com/llvm/llvm-project/blob/release/10.x/clang-tools-extra/clangd/Preamble.cpp#L101-L107) which would just return the old one if it was still valid.

For a while now we've had async preambles which are more complicated but use the same underlying mechanism. Each file has an ASTWorker thread and a PreambleThread. When the ASTWorker thread wants to reuse preamble, it notifies the PreambleThread "hey, maybe rebuild the preamble?" but meanwhile it charges on using the old stale preamble. The preamble asynchronously performs the validity check, rebuilds the preamble if needed, and eventually informs the ASTWorker which ensures the up-to-date preamble is eventually used.

This is a "pull" system: we only check if the preamble is valid when we tried to use it, i.e. when the main-file changed. If you just touch a header on disk but do nothing else, we won't rebuild either the main file or the preamble.

In the comments of ClangdServer::reparseOpenFilesIfNeeded(), I see:

/ Requests a reparse of currently opened files using their latest source.
/ This will typically only rebuild if something other than the source has
/ changed (e.g. the CDB yields different flags, or files included in the
/ preamble have been modified).

Because the above is a pull system, editing a header doesn't update e.g. diagnostics in files that include that header.
So this is a workaround: it requests all files to be rebuilt from current sources, so we pull on all preambles.
Then at every layer we try to ensure this does no work if nothing has changed :-)

In practice we call this in response to didSave (user edited+saved a header in their editor), we could potentially call it in response to changes on disk as Nathan suggested, and I think we have a custom integration somewhere that calls it when we know externally that compile flags have changed.

[ChuanqiXu]

Got it. Thanks for your explanation. I can continue my experiment : )

[ChuanqiXu]

I sent the next patch at: https://github.com/llvm/llvm-project/pull/66462

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   Headers.cpp
   HeaderSourceSwitch.cpp
   HeuristicResolver.cpp
   Hover.cpp
   IncludeCleaner.cpp
   IncludeFixer.cpp
   InlayHints.cpp
   JSONTransport.cpp
+  ModulesManager.cpp
   PathMapping.cpp
   Protocol.cpp
   Quality.cpp
   ParsedAST.cpp
   Preamble.cpp
   RIFF.cpp
   Selection.cpp
   SemanticHighlighting.cpp
clang_target_link_libraries(clangDaemon
   clangLex
   clangSema
   clangSerialization
   clangTooling
   clangToolingCore
   clangToolingInclusions
   clangToolingInclusionsStdlib
   clangToolingSyntax
+  clangDependencyScanning
   )
 
 target_link_libraries(clangDaemon
   PRIVATE
   ${LLVM_PTHREAD_LIB}
 
   clangIncludeCleaner
   clangPseudo

clang-tools-extra/clangd/ClangdLSPServer.h

class ClangdLSPServer : private ClangdServer::Callbacks,
                         private LSPBinder::RawOutgoing {
 public:
   struct Options : ClangdServer::Options {
     /// Supplies configuration (overrides ClangdServer::ContextProvider).
     config::Provider *ConfigProvider = nullptr;
     /// Look for compilation databases, rather than using compile commands
     /// set via LSP (extensions) only.
     bool UseDirBasedCDB = true;
+    /// Enable experimental support for modules.
+    bool ExperimentalModulesSupport = false;
     /// The offset-encoding to use, or std::nullopt to negotiate it over LSP.
     std::optional<OffsetEncoding> Encoding;
     /// If set, periodically called to release memory.
     /// Consider malloc_trim(3)
     std::function<void()> MemoryCleanup = nullptr;
 
     /// Per-feature options. Generally ClangdServer lets these vary
     /// per-request, but LSP allows limited/no customizations.

clang-tools-extra/clangd/ClangdLSPServer.cpp

 //===--- ClangdLSPServer.cpp - LSP server ------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ClangdLSPServer.h"
 #include "ClangdServer.h"
 #include "CodeComplete.h"
 #include "CompileCommands.h"
 #include "Diagnostics.h"
 #include "Feature.h"
 #include "GlobalCompilationDatabase.h"
 #include "LSPBinder.h"
+#include "ModulesManager.h"
 #include "Protocol.h"
 #include "SemanticHighlighting.h"
 #include "SourceCode.h"
 #include "TUScheduler.h"
 #include "URI.h"
 #include "refactor/Tweak.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"
void ClangdLSPServer::onInitialize(const InitializeParams &Params,
   Opts.ImplicitCancellation = !Params.capabilities.CancelsStaleRequests;
   Opts.PublishInactiveRegions = Params.capabilities.InactiveRegions;
 
   if (Opts.UseDirBasedCDB) {
     DirectoryBasedGlobalCompilationDatabase::Options CDBOpts(TFS);
     if (const auto &Dir = Params.initializationOptions.compilationDatabasePath)
       CDBOpts.CompileCommandsDir = Dir;
     CDBOpts.ContextProvider = Opts.ContextProvider;
+
+    if (Opts.ExperimentalModulesSupport)
+      BaseCDB =
+          std::make_unique<DirectoryBasedModulesGlobalCompilationDatabase>(
+              CDBOpts, Opts.AsyncThreadsCount);
+    else
       BaseCDB =
           std::make_unique<DirectoryBasedGlobalCompilationDatabase>(CDBOpts);
   }
   auto Mangler = CommandMangler::detect();
   Mangler.SystemIncludeExtractor =
       getSystemIncludeExtractor(llvm::ArrayRef(Opts.QueryDriverGlobs));
   if (Opts.ResourceDir)
     Mangler.ResourceDir = *Opts.ResourceDir;
   CDB.emplace(BaseCDB.get(), Params.initializationOptions.fallbackFlags,
               std::move(Mangler));

clang-tools-extra/clangd/ClangdServer.h

 #include <optional>
 #include <string>
 #include <type_traits>
 #include <utility>
 #include <vector>
 
 namespace clang {
 namespace clangd {
+
 /// Manages a collection of source files and derived data (ASTs, indexes),
 /// and provides language-aware features such as code completion.
 ///
 /// The primary client is ClangdLSPServer which exposes these features via
 /// the Language Server protocol. ClangdServer may also be embedded directly,
 /// though its API is not stable over time.
 ///
 /// ClangdServer should be used from a single thread. Many potentially-slow

clang-tools-extra/clangd/GlobalCompilationDatabase.h

 namespace clangd {
 
 struct ProjectInfo {
   // The directory in which the compilation database was discovered.
   // Empty if directory-based compilation database discovery was not used.
   std::string SourceRoot;
 };
 
+class ModulesManager;
+
 /// Provides compilation arguments used for parsing C and C++ files.
 class GlobalCompilationDatabase {
 public:
   virtual ~GlobalCompilationDatabase() = default;
 
   /// If there are any known-good commands for building this file, returns one.
   virtual std::optional<tooling::CompileCommand>
   getCompileCommand(PathRef File) const = 0;
 
   /// Finds the closest project to \p File.
   virtual std::optional<ProjectInfo> getProjectInfo(PathRef File) const {
     return std::nullopt;
   }
 
+  virtual std::vector<std::string> getAllFilesInProjectOf(PathRef File) const {
+    return {};
+  }
+
   /// Makes a guess at how to build a file.
   /// The default implementation just runs clang on the file.
   /// Clangd should treat the results as unreliable.
   virtual tooling::CompileCommand getFallbackCommand(PathRef File) const;
 
   /// If the CDB does any asynchronous work, wait for it to complete.
   /// For use in tests.
   virtual bool blockUntilIdle(Deadline D) const { return true; }
 
   using CommandChanged = Event<std::vector<std::string>>;
   /// The callback is notified when files may have new compile commands.
   /// The argument is a list of full file paths.
   CommandChanged::Subscription watch(CommandChanged::Listener L) const {
     return OnCommandChanged.observe(std::move(L));
   }
 
+  virtual ModulesManager *getModulesManager() const { return nullptr; }
+
 protected:
   mutable CommandChanged OnCommandChanged;
 };
 
 // Helper class for implementing GlobalCompilationDatabases that wrap others.
 class DelegatingCDB : public GlobalCompilationDatabase {
 public:
   DelegatingCDB(const GlobalCompilationDatabase *Base);
   DelegatingCDB(std::unique_ptr<GlobalCompilationDatabase> Base);
 
   std::optional<tooling::CompileCommand>
   getCompileCommand(PathRef File) const override;
 
   std::optional<ProjectInfo> getProjectInfo(PathRef File) const override;
+  virtual std::vector<std::string>
+  getAllFilesInProjectOf(PathRef File) const override;
 
   tooling::CompileCommand getFallbackCommand(PathRef File) const override;
 
   bool blockUntilIdle(Deadline D) const override;
 
+  virtual ModulesManager *getModulesManager() const override;
+
 private:
   const GlobalCompilationDatabase *Base;
   std::unique_ptr<GlobalCompilationDatabase> BaseOwner;
   CommandChanged::Subscription BaseChanged;
 };
 
 /// Gets compile args from tooling::CompilationDatabases built for parent
 /// directories.
public:
   /// Any extra flags will be added.
   /// Might trigger OnCommandChanged, if CDB wasn't broadcasted yet.
   std::optional<tooling::CompileCommand>
   getCompileCommand(PathRef File) const override;
 
   /// Returns the path to first directory containing a compilation database in
   /// \p File's parents.
   std::optional<ProjectInfo> getProjectInfo(PathRef File) const override;
+  virtual std::vector<std::string>
+  getAllFilesInProjectOf(PathRef File) const override;
 
   bool blockUntilIdle(Deadline Timeout) const override;
 
-private:
+protected:
   Options Opts;
 
   class DirectoryCache;
   // Keyed by possibly-case-folded directory path.
   // We can hand out pointers as they're stable and entries are never removed.
   mutable llvm::StringMap<DirectoryCache> DirCaches;
   mutable std::mutex DirCachesMutex;
 
protected:
 
   // Performs broadcast on governed files.
   void broadcastCDB(CDBLookupResult Res) const;
 
   // cache test calls lookupCDB directly to ensure valid/invalid times.
   friend class DirectoryBasedGlobalCompilationDatabaseCacheTest;
 };
 
+class DirectoryBasedModulesGlobalCompilationDatabase
+    : public DirectoryBasedGlobalCompilationDatabase {
+public:
+  DirectoryBasedModulesGlobalCompilationDatabase(
+      const DirectoryBasedGlobalCompilationDatabase::Options &CDB,
+      unsigned AsyncThreadsCount);
+
+  virtual ModulesManager *getModulesManager() const override {
+    return ModuleMgr.get();
+  }
+
+  virtual std::optional<tooling::CompileCommand>
+  getCompileCommand(PathRef File) const override;
+
+  bool blockUntilIdle(Deadline D) const override;
+
+  std::optional<tooling::CompileCommand>
+  getOriginalCompileCommand(PathRef File) const;
+
+  const ThreadsafeFS &getThreadsafeFS() const { return Opts.TFS; }
+
+private:
+  llvm::SmallString<128> getModuleFilesCachePrefix(PathRef File) const;
+  llvm::SmallString<128> getMappedModuleFiles(PathRef) const;
+
+  std::unique_ptr<ModulesManager> ModuleMgr;
+
+  GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
+};
+
 /// Extracts system include search path from drivers matching QueryDriverGlobs
 /// and adds them to the compile flags.
 /// Returns null when \p QueryDriverGlobs is empty.
 using SystemIncludeExtractorFn = llvm::unique_function<void(
     tooling::CompileCommand &, llvm::StringRef) const>;
 SystemIncludeExtractorFn
 getSystemIncludeExtractor(llvm::ArrayRef<std::string> QueryDriverGlobs);
 

clang-tools-extra/clangd/GlobalCompilationDatabase.cpp

 //===--- GlobalCompilationDatabase.cpp ---------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "GlobalCompilationDatabase.h"
 #include "Config.h"
 #include "FS.h"
+#include "ModulesManager.h"
 #include "SourceCode.h"
 #include "support/Logger.h"
 #include "support/Path.h"
 #include "support/Threading.h"
 #include "support/ThreadsafeFS.h"
 #include "clang/Tooling/ArgumentsAdjusters.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/CompilationDatabasePluginRegistry.h"
DirectoryBasedGlobalCompilationDatabase::getProjectInfo(PathRef File) const {
   Req.FreshTime = Req.FreshTimeMissing =
       std::chrono::steady_clock::time_point::min();
   auto Res = lookupCDB(Req);
   if (!Res)
     return std::nullopt;
   return Res->PI;
 }
 
+std::vector<std::string>
+DirectoryBasedGlobalCompilationDatabase::getAllFilesInProjectOf(
+    PathRef File) const {
+  CDBLookupRequest Req;
+  Req.FileName = File;
+  Req.ShouldBroadcast = false;
+  Req.FreshTime = Req.FreshTimeMissing =
+      std::chrono::steady_clock::time_point::min();
+  auto Res = lookupCDB(Req);
+  if (!Res) {
+    log("Failed to get the Compilation Database?");
+    return {};
+  }
+  return Res->CDB->getAllFiles();
+}
+
 OverlayCDB::OverlayCDB(const GlobalCompilationDatabase *Base,
                        std::vector<std::string> FallbackFlags,
                        CommandMangler Mangler)
     : DelegatingCDB(Base), Mangler(std::move(Mangler)),
       FallbackFlags(std::move(FallbackFlags)) {}
 
 std::optional<tooling::CompileCommand>
 OverlayCDB::getCompileCommand(PathRef File) const {

 }
 
 std::optional<ProjectInfo> DelegatingCDB::getProjectInfo(PathRef File) const {
   if (!Base)
     return std::nullopt;
   return Base->getProjectInfo(File);
 }
 
+std::vector<std::string>
+DelegatingCDB::getAllFilesInProjectOf(PathRef File) const {
+  if (!Base)
+    return {};
+  return Base->getAllFilesInProjectOf(File);
+}
+
 tooling::CompileCommand DelegatingCDB::getFallbackCommand(PathRef File) const {
   if (!Base)
     return GlobalCompilationDatabase::getFallbackCommand(File);
   return Base->getFallbackCommand(File);
 }
 
 bool DelegatingCDB::blockUntilIdle(Deadline D) const {
   if (!Base)
     return true;
   return Base->blockUntilIdle(D);
 }
 
+ModulesManager *DelegatingCDB::getModulesManager() const {
+  if (!Base)
+    return nullptr;
+  return Base->getModulesManager();
+}
+
+DirectoryBasedModulesGlobalCompilationDatabase::
+    DirectoryBasedModulesGlobalCompilationDatabase(
+        const DirectoryBasedGlobalCompilationDatabase::Options &options,
+        unsigned AsyncThreadsCount)
+    : DirectoryBasedGlobalCompilationDatabase(options) {
+  ModuleMgr = std::make_unique<ModulesManager>(*this, AsyncThreadsCount);
+
+  CommandsChanged = watch([ModuleMgr = ModuleMgr.get()](
+                              const std::vector<std::string> &ChangedFiles) {
+    ModuleMgr->UpdateBunchFiles(ChangedFiles);
+  });
+}
+
+llvm::SmallString<128>
+DirectoryBasedModulesGlobalCompilationDatabase::getModuleFilesCachePrefix(
+    PathRef File) const {
+  std::optional<ProjectInfo> PI = getProjectInfo(File);
+  if (!PI)
+    return {};
+
+  llvm::SmallString<128> Result(PI->SourceRoot);
+  llvm::sys::path::append(Result, ".cache");
+  llvm::sys::path::append(Result, "clangd");
+  llvm::sys::path::append(Result, "module_files");
+
+  llvm::sys::fs::create_directories(Result, /*IgnoreExisting*/ true);
+  return Result;
+}
+
+llvm::SmallString<128>
+DirectoryBasedModulesGlobalCompilationDatabase::getMappedModuleFiles(
+    PathRef File) const {
+  std::string ModuleFileName = ModuleMgr->GetModuleInterfaceName(File);
+
+  // Replace ":" in the module name with "-" to follow clang's style. Since ":"
+  // is not a valid character in some file systems.
+  auto [PrimaryName, PartitionName] =
+      llvm::StringRef(ModuleFileName).split(":");
+  if (!PartitionName.empty())
+    ModuleFileName = PrimaryName.str() + "-" + PartitionName.str();
+
+  llvm::SmallString<128> Result = getModuleFilesCachePrefix(File);
+  llvm::sys::path::append(Result, ModuleFileName + ".pcm");
+  return Result;
+}
+
+std::optional<tooling::CompileCommand>
+DirectoryBasedModulesGlobalCompilationDatabase::getOriginalCompileCommand(
+    PathRef File) const {
+  return DirectoryBasedGlobalCompilationDatabase::getCompileCommand(File);
+}
+
+bool DirectoryBasedModulesGlobalCompilationDatabase::blockUntilIdle(
+    Deadline D) const {
+  ModuleMgr->waitUntilInitialized();
+  return DirectoryBasedGlobalCompilationDatabase::blockUntilIdle(D);
+}
+
+std::optional<tooling::CompileCommand>
+DirectoryBasedModulesGlobalCompilationDatabase::getCompileCommand(
+    PathRef File) const {
+  auto Result =
+      DirectoryBasedGlobalCompilationDatabase::getCompileCommand(File);
+  if (!Result)
+    return std::nullopt;
+
+  if (!ModuleMgr->HasGraph() || !ModuleMgr->IsInGraph(File))
+    return Result;
+
+  if (ModuleMgr->IsModuleInterface(File))
+    Result->Output = getMappedModuleFiles(File).str();
+
+  std::vector<std::string> CommandLine;
+  CommandLine.reserve(Result->CommandLine.size() + 1);
+
+  CommandLine.emplace_back(Result->CommandLine[0]);
+  llvm::SmallString<128> ModuleOutputPrefix = getModuleFilesCachePrefix(File);
+  CommandLine.emplace_back(
+      llvm::Twine("-fprebuilt-module-path=" + ModuleOutputPrefix).str());
+
+  for (std::size_t I = 1; I < Result->CommandLine.size(); I++) {
+    const std::string &Arg = Result->CommandLine[I];
+    const auto &[Left, Right] = StringRef(Arg).split("=");
+
+    // Remove original `-fmodule-file=<module-name>=<module-path>` form.
+    if (Left == "-fmodule-file" && Right.contains("="))
+      continue;
+
+    CommandLine.emplace_back(Arg);
+  }
+
+  Result->CommandLine = CommandLine;
+
+  return Result;
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/ModulesManager.h

+//===--- ModulesManager.h ----------------------------------------*- C++-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "GlobalCompilationDatabase.h"
+#include "support/Path.h"
+#include "support/Threading.h"
+
+#include "clang/Frontend/FrontendAction.h"
+#include "clang/Tooling/DependencyScanning/DependencyScanningService.h"
+#include "clang/Tooling/DependencyScanning/DependencyScanningTool.h"
+#include "llvm/ADT/ConcurrentHashtable.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringSet.h"
+
+#include <map>
+#include <optional>
+#include <set>
+#include <string>
+#include <vector>
+
+namespace clang::clangd {
+
+namespace detail {
+/// A simple wrapper for AsyncTaskRunner and Semaphore to run modules related
+/// task - Scanning, Generating Module Interfaces - concurrently.
+class ModulesTaskRunner {
+  ModulesTaskRunner(unsigned AsyncThreadsCount) : Barrier(AsyncThreadsCount) {
+    if (AsyncThreadsCount > 0)
+      Runner.emplace();
+  }
+
+  friend class clang::clangd::ModulesManager;
+
+public:
+  void RunTask(llvm::unique_function<void()> Task,
+               const llvm::Twine &Name = "");
+
+  void wait();
+
+private:
+  std::optional<AsyncTaskRunner> Runner;
+  Semaphore Barrier;
+};
+
+/// A data structure to describe the C++20 named modules dependency information
+/// of the project. So that a file which doesn't declare a module name nor uses
+/// a modules won't be recorded in the graph.
+///
+/// Note that this graph is not thread safe. The thread safety is guaranteed by
+/// its owner.
+class ModulesDependencyGraph {
+  struct ModulesDependencyNode {
+    ModulesDependencyNode(PathRef Name) : Name(Name.str()) {}
+
+    /// The corresponding filename of the node.
+    std::string Name;
+    /// The module unit name of the node (if it provides).
+    std::optional<std::string> Provided;
+    /// The set of names that the node directly requires. The transitively
+    /// required names are not recorded here.
+    llvm::StringSet<> Requires;
+
+    /// Update Provided and Requires information by provided P1689 rule.
+    ///
+    /// @return false if the node doesn't change. Return true otherwise.
+    bool
+    UpdateProvidedAndRequires(const tooling::dependencies::P1689Rule &Rule);
+
+    /// The users of the current node. The node should be in the Deps for the
+    /// users.
+    std::set<ModulesDependencyNode *> Users;
+    /// The dependent nodes of the current node. Note that it is possible that
+    /// `Requires.size() > Deps.size()` since there are possibly third party
+    /// modules for which we can't its source code. But the size of Deps should
+    /// never be larger than Requires.
+    std::set<ModulesDependencyNode *> Deps;
+
+    /// The corresponding BMI path of the current Node. This is only meaningful
+    /// if the current node is a module interface.
+    ///
+    /// When the BMIPath is not set, it implies that we know nothing about its
+    /// BMI. When one node has empty BMIPath (""), it implies that the node is
+    /// not able to be compiled. When one node has non-empty BMIPath, it implies
+    /// that the node has a meaningfull BMI and all the (transitively) dependent
+    /// nodes have meaningful BMI.
+    std::optional<std::string> BMIPath;
+  };
+
+public:
+  ModulesDependencyGraph() = default;
+  ModulesDependencyGraph(const ModulesDependencyGraph &) = delete;
+  ModulesDependencyGraph(ModulesDependencyGraph &&) = delete;
+  ModulesDependencyGraph operator=(const ModulesDependencyGraph &) = delete;
+  ModulesDependencyGraph operator=(ModulesDependencyGraph &&) = delete;
+  ~ModulesDependencyGraph() = default;
+
+  bool empty() const { return Nodes.empty(); }
+  size_t size() const { return Nodes.size(); }
+
+  bool IsInGraph(PathRef Path) const { return Nodes.count(Path.str()); }
+  bool IsModuleInterface(PathRef Path) const {
+    return IsInGraph(Path) && Nodes.at(Path.str())->Provided;
+  }
+  std::string GetModuleInterfaceName(PathRef Path) const {
+    assert(IsModuleInterface(Path));
+    return *Nodes.at(Path.str())->Provided;
+  }
+
+  /// Whether if all the (transitive) dependencies have valid BMI.
+  ///
+  /// Note that this doesn't include third party modules for which the source
+  /// codes can't be found.
+  bool IsReadyToCompile(PathRef Filename) const;
+  /// Whether there is any dependencies has invalid BMI.
+  bool HasInvalidDependencies(PathRef Filename) const;
+
+  const ModulesDependencyNode *getNode(PathRef Path) const {
+    if (!Nodes.count(Path.str()))
+      return nullptr;
+
+    return Nodes.at(Path.str()).get();
+  }
+
+  /// Get the direct users.
+  std::set<ModulesDependencyNode *> getNodeUsers(PathRef Path) const {
+    if (!Nodes.count(Path.str()))
+      return {};
+
+    return Nodes.at(Path.str())->Users;
+  }
+
+  /// Get all transitive users.
+  std::set<ModulesDependencyNode *> getAllUsers(PathRef Path) const;
+
+  void clear() {
+    Nodes.clear();
+    ModuleMapper.clear();
+  }
+
+  bool SetBMIPath(PathRef Filename, PathRef BMIPath);
+
+  /// Update/Insert a node in/to the graph. When all of \p AllowInsertNewNode ,
+  /// \p AllowUpdateModuleMapper and \p AllowUpdateDependency are false, it is
+  /// thread safe to run `UpdateSingleNode` parallelly. If the caller want to
+  /// run `UpdateSingleNode` parallelly, it is the responsibility of the caller
+  /// to call `InsertNewNode` ahead of time and call `reconstructModuleMapper`
+  /// and `UpdateDependencies` later to maintain the validability of the graph.
+  void UpdateSingleNode(PathRef Filename,
+                        const tooling::dependencies::P1689Rule &Rule,
+                        bool AllowInsertNewNode = true,
+                        bool AllowUpdateModuleMapper = true,
+                        bool AllowUpdateDependency = true);
+  /// Insert new nodes to the graph. This shouldn't be called if the caller
+  /// don't want to run `UpdateSingleNode` parallelly.
+  void InsertNewNode(PathRef Filename);
+  /// Update the dependency information after updating node(s). This shouldn't
+  /// be called if the caller don't want to run `UpdateSingleNode` parallelly.
+  void UpdateDependencies(const llvm::StringSet<> &Files,
+                          bool RecalculateEdges = true);
+
+  /// Construct the module map from module name to ModulesDependencyNode* after
+  /// updating node(s). This shouldn't be called if the caller don't want to run
+  /// `UpdateSingleNode` parallelly.
+  void reconstructModuleMapper();
+
+  /// If the specified Path has (non-transitively) third party dependencies.
+  /// This is only called by testing purpose.
+  bool HasThirdpartyDependencies(PathRef Path) const;
+
+private:
+  void UpdateModuleMapper(PathRef Filename,
+                          const tooling::dependencies::P1689Rule &Rule);
+
+  /// Map from source file path to ModulesDependencyNode*.
+  llvm::StringMap<std::unique_ptr<ModulesDependencyNode>> Nodes;
+  /// Map from the module name to ModulesDependencyNode*. This is a helper
+  /// strucutre to build the depenendcy graph faster. So it doesn't own the
+  /// nodes. It is OK for this to get ready before calling UpdateDependencies.
+  llvm::StringMap<ModulesDependencyNode *> ModuleMapper;
+};
+} // namespace detail
+
+/// A manager to manage the dependency information of modules and module files
+/// states. The users can use `IsReadyToCompile(Path)` to get if it is Ok to
+/// compile the file specified by `Path`. In case it is not ready, the user can
+/// use the following pattern to wait for it to gets ready:
+///
+///     ModuleMgr.addCallbackAfterReady(Path, [] () {
+///       notify it is ready;
+///     });
+///     ModuleMgr.GenerateModuleInterfacesFor(Path);
+///     wait for it to get ready.
+///
+/// Every time we meet a new file or a file get changed, we should call
+/// `UpdateNode(PathRef)` to try to update its status in the graph no matter if
+/// it was related to modules before. Since it is possible that the change of
+/// the file is to introduce module related things. So it should be job of
+/// ModulesManager to decide whether or not it is related to modules.
+class ModulesManager {
+public:
+  ModulesManager(const DirectoryBasedModulesGlobalCompilationDatabase &CDB,
+                 unsigned AsyncThreadsCount);
+  ~ModulesManager();
+
+  /// If Filename is not related to moduls, e.g, not a module unit nor import
+  /// any modules, nothing will happen. Otherwise the modules manager will try
+  /// to update the modules graph responsitively.
+  void UpdateNode(PathRef Filename);
+  /// Update a lot of files at the same time. This should only be called by
+  /// DirectoryBasedModulesGlobalCompilationDatabase as a callback when finding
+  /// new compilation database.
+  void UpdateBunchFiles(const std::vector<std::string> &Files);
+
+  /// Whether we have atleast one node in the modules graph.
+  bool HasGraph() const;
+  /// If the specified file is in the graph.
+  bool IsInGraph(PathRef Path) const;
+  /// If the specified file is a module interface unit.
+  bool IsModuleInterface(PathRef Path) const;
+  std::string GetModuleInterfaceName(PathRef Path) const;
+
+  /// Helper functions for testing
+  bool IsDirectlyDependent(PathRef A, PathRef B) const;
+  /// @return the number of nodes in the graph.
+  size_t GraphSize() const;
+  bool HasThirdpartyDependencies(PathRef A) const;
+
+  /// We'll initialize the graph asynchronously. It is necessary for tests
+  /// to wait for the graph get initialized.
+  void waitUntilInitialized() const;
+
+  /// @return If the BMIs of the dependencies for the specified file are valid
+  /// already.
+  bool IsReadyToCompile(PathRef Filename) const;
+  /// @return true if there is any (transitive) dependencies are invalid. False
+  /// otherwise, this doesn't include third party modules.
+  bool HasInvalidDependencies(PathRef Filename) const;
+
+  /// Add a callback which will be called when the corresponding source file
+  /// gets ready. This requires `!IsReadyToCompile(Filename)` and
+  /// `!HasInvalidDependencies(Filename)`.
+  ///
+  /// @param ReadyCallback the callback get called when the file specified by
+  /// Filename gets ready.
+  /// @param FailureCallback the callback get called when file specified by
+  /// Filename are known not to be ready. It is possible that its dependencies
+  /// are known not to be able to be compiled. If not specified, it will be the
+  /// same with ReadyCallback.
+  void addCallbackAfterReady(PathRef Filename,
+                             std::function<void()> ReadyCallback,
+                             std::function<void()> FailureCallback = nullptr);
+
+  /// Generate module files for file specified by Path. This will generate
+  /// module files for the transitively dependencies. It requires there is no
+  /// invalid dependencies.
+  void GenerateModuleInterfacesFor(PathRef Path);
+
+private:
+  void GenerateModuleInterface(PathRef Path);
+
+  /// Invoke ClangScanDeps to get P1689 rule for the specified file.
+  std::optional<tooling::dependencies::P1689Rule>
+  getRequiresAndProvide(PathRef Path);
+
+  detail::ModulesDependencyGraph Graph;
+
+  /// A mutex for the graph. Any operation to the graph should be guarded by the
+  /// mutex.
+  mutable std::mutex Mutex;
+
+  /// A helper class to track the scheduled tasks to generate module files to
+  /// not schedule duplicated task to generate module files for the same file.
+  llvm::StringSet<> ScheduledInterfaces;
+
+  /// A map from path of source files to the callbacks when the file gets ready
+  /// or failed to get ready.
+  llvm::StringMap<llvm::SmallVector<
+      std::pair<std::function<void()>, std::function<void()>>, 8>>
+      WaitingCallables;
+  /// All the operations for WaitingCallables should be guarded by the mutex.
+  mutable std::mutex WaitingCallablesMutex;
+  /// Set BMIPath to the node specified by Filename and run the corresponding
+  /// callbacks (if any). If the BMIPath is empty, it implies that the node is
+  /// invalid to compile.
+  void setBMIPath(PathRef Filename, PathRef BMIPath);
+
+  const DirectoryBasedModulesGlobalCompilationDatabase &CDB;
+  clang::tooling::dependencies::DependencyScanningService Service;
+
+  enum GraphInitState { Uninitialized, Initializing, Initialized };
+  std::atomic<unsigned> InitializeState = Uninitialized;
+  mutable std::mutex InitializationMutex;
+  mutable std::condition_variable InitCV;
+
+  /// Atomatically test if the graph is uninitialized. And if yes, change its
+  /// value to Initializing atomatically. This should only be called before
+  /// InitializeGraph
+  bool IsUnitialized() {
+    unsigned UninitializedState = Uninitialized;
+    return InitializeState.compare_exchange_strong(UninitializedState,
+                                                   Initializing);
+  }
+
+  /// Lock the whole graph until is initialized. This is an abbrevation for:
+  ///
+  ///   waitUntilInitialized();
+  ///   std::lock_guard<std::mutex> Lock(Mutex);
+  [[nodiscard]] std::lock_guard<std::mutex> lockGraph() const {
+    waitUntilInitialized();
+    return std::lock_guard(Mutex);
+  }
+
+  /// Initialize the graph. Modules manager will try to do it asynchronously if
+  /// we have the resources.
+  void InitializeGraph(PathRef Filename);
+
+  unsigned AsyncThreadsCount = 0;
+  detail::ModulesTaskRunner Runner;
+};
+
+} // namespace clang::clangd

clang-tools-extra/clangd/ModulesManager.cpp

+//===--- ModulesManager.cpp --------------------------------------*- C++-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "ModulesManager.h"
+#include "Compiler.h"
+#include "support/Logger.h"
+
+#include "clang/Frontend/FrontendActions.h"
+#include "clang/Tooling/Tooling.h"
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/ScopeExit.h"
+
+using namespace clang;
+using namespace clang::clangd;
+using namespace clang::tooling::dependencies;
+
+ModulesManager::ModulesManager(
+    const DirectoryBasedModulesGlobalCompilationDatabase &CDB,
+    unsigned AsyncThreadsCount)
+    : CDB(CDB), Service(ScanningMode::CanonicalPreprocessing,
+                        ScanningOutputFormat::P1689),
+      AsyncThreadsCount(AsyncThreadsCount), Runner(AsyncThreadsCount) {}
+
+ModulesManager::~ModulesManager() { Runner.wait(); }
+
+bool clang::clangd::detail::ModulesDependencyGraph::SetBMIPath(
+    PathRef Filename, PathRef BMIPath) {
+  if (!Nodes.count(Filename))
+    return false;
+
+  Nodes[Filename]->BMIPath = BMIPath;
+  return true;
+}
+
+std::optional<P1689Rule> ModulesManager::getRequiresAndProvide(PathRef Name) {
+  std::optional<tooling::CompileCommand> Cmd =
+      CDB.getOriginalCompileCommand(Name);
+
+  if (!Cmd)
+    return std::nullopt;
+
+  using namespace clang::tooling::dependencies;
+
+  DependencyScanningTool ScanningTool(Service);
+
+  std::string MakeformatOutput;
+  std::string MakeformatOutputPath;
+  llvm::Expected<P1689Rule> P1689Rule =
+      ScanningTool.getP1689ModuleDependencyFile(
+          *Cmd, Cmd->Directory, MakeformatOutput, MakeformatOutputPath);
+
+  if (!P1689Rule)
+    return std::nullopt;
+
+  return *P1689Rule;
+}
+
+void ModulesManager::UpdateBunchFiles(const std::vector<std::string> &Files) {
+  if (IsUnitialized())
+    return InitializeGraph(Files.front());
+
+  waitUntilInitialized();
+
+  // If the size of new files are not so many, maybe it is better
+  // to not re-initialize the whole graph.
+  //
+  // Maybe we need a better fine-tuned condition.
+  if (Files.size() < Graph.size() / 2) {
+    for (const std::string &File : Files)
+      UpdateNode(File);
+
+    return;
+  }
+
+  {
+    std::lock_guard<std::mutex> Lock(Mutex);
+    Graph.clear();
+    InitializeState = Initializing;
+  }
+  InitializeGraph(Files.front());
+}
+
+void ModulesManager::UpdateNode(PathRef Filename) {
+  std::optional<P1689Rule> Rule = getRequiresAndProvide(Filename);
+  if (!Rule)
+    return;
+
+  auto _ = lockGraph();
+  Graph.UpdateSingleNode(Filename, *Rule);
+}
+
+void ModulesManager::waitUntilInitialized() const {
+  if (InitializeState == Initializing) {
+    std::unique_lock<std::mutex> Lock(InitializationMutex);
+    InitCV.wait(Lock, [this]() { return InitializeState == Initialized; });
+  }
+}
+
+// TODO: Try to use the existing BMIs, which is created in last invocation of
+// clangd.
+void ModulesManager::InitializeGraph(PathRef Filename) {
+#ifndef NDEBUG
+  assert(Graph.empty());
+  assert(InitializeState == Initializing &&
+         "InitializeState should be set before calling InitializeGraph.");
+#endif
+
+  // Initialization may be slow. Consider to do it asynchronously.
+  auto Task = [this, &CDB = CDB, &Graph = Graph, &Mutex = Mutex,
+               Filename = Filename.str(), &Runner = Runner]() {
+    std::vector<std::string> AllFiles = CDB.getAllFilesInProjectOf(Filename);
+    llvm::StringSet<> ModuleRelatedFiles;
+
+    // In case we don't have enough resources, run it locally.
+    // Note that the current task may use async resources.
+    if (AsyncThreadsCount <= 1) {
+      for (const std::string &File : AllFiles) {
+        std::optional<P1689Rule> Rule = getRequiresAndProvide(File);
+        if (!Rule)
+          continue;
+
+        std::lock_guard<std::mutex> Lock(Mutex);
+        ModuleRelatedFiles.insert(File);
+        Graph.UpdateSingleNode(File, *Rule,
+                               /*InsertNewNode*/ true,
+                               /*AllowUpdateModuleMapper*/ false,
+                               /*UpdateDependency*/ false);
+      }
+    } else {
+      // We have threads. Let's try to scanning the graph pararrelly.
+      std::atomic<unsigned> UnfinishedTaskNum = AllFiles.size();
+      std::mutex FinishedMu;
+      std::condition_variable FinishedCV;
+
+      std::mutex Mu;
+      for (const auto &File : AllFiles)
+        Runner.RunTask([this, &Graph, File, &ModuleRelatedFiles, &FinishedCV,
+                        &UnfinishedTaskNum, &Mu]() mutable {
+          std::optional<P1689Rule> Rule = getRequiresAndProvide(File);
+          if (!Rule)
+            return;
+
+          // Try to make the critical section as short as possible.
+          {
+            std::lock_guard<std::mutex> Lock(Mu);
+            Graph.InsertNewNode(File);
+            ModuleRelatedFiles.insert(File);
+          }
+
+          // It is thread safe now by design.
+          Graph.UpdateSingleNode(File, *Rule,
+                                 /*InsertNewNode*/ false,
+                                 /*AllowUpdateModuleMapper*/ false,
+                                 /*UpdateDependency*/ false);
+
+          UnfinishedTaskNum--;
+
+          if (!UnfinishedTaskNum)
+            FinishedCV.notify_all();
+        });
+
+      std::unique_lock<std::mutex> Lock(FinishedMu);
+      FinishedCV.wait(
+          Lock, [&UnfinishedTaskNum]() { return UnfinishedTaskNum == 0; });
+    }
+
+    std::lock_guard<std::mutex> Lock(Mutex);
+    // Now construct the module mapper in one go.
+    Graph.reconstructModuleMapper();
+    Graph.UpdateDependencies(ModuleRelatedFiles);
+    InitializeState = Initialized;
+    InitCV.notify_all();
+  };
+
+  Runner.RunTask(std::move(Task));
+}
+
+void clang::clangd::detail::ModulesDependencyGraph::reconstructModuleMapper() {
+  ModuleMapper.clear();
+
+  for (auto &&Key : Nodes.keys())
+    if (Nodes[Key]->Provided)
+      ModuleMapper[*Nodes[Key]->Provided] = Nodes[Key].get();
+}
+
+bool clang::clangd::detail::ModulesDependencyGraph::ModulesDependencyNode::
+    UpdateProvidedAndRequires(const P1689Rule &Rule) {
+  bool DependencyChanged =
+      Rule.Provides ? (Provided != Rule.Provides->ModuleName) : !Provided;
+
+  if (DependencyChanged) {
+    if (Rule.Provides)
+      Provided = Rule.Provides->ModuleName;
+    else
+      Provided = std::nullopt;
+  }
+
+  DependencyChanged |= (Requires.size() != Rule.Requires.size());
+  llvm::StringSet<> RequiresTmp = Requires;
+  for (const P1689ModuleInfo &Required : Rule.Requires) {
+    auto [_, Inserted] = Requires.insert(Required.ModuleName);
+    DependencyChanged |= Inserted;
+    RequiresTmp.erase(Required.ModuleName);
+  }
+
+  DependencyChanged |= !RequiresTmp.empty();
+  for (auto &NotEliminated : RequiresTmp)
+    if (Requires.count(NotEliminated.getKey()))
+      Requires.erase(NotEliminated.getKey());
+
+  return DependencyChanged;
+}
+
+void clang::clangd::detail::ModulesDependencyGraph::InsertNewNode(
+    PathRef Filename) {
+  if (!Nodes.count(Filename))
+    Nodes.insert({Filename, std::make_unique<ModulesDependencyNode>(Filename)});
+}
+
+void clang::clangd::detail::ModulesDependencyGraph::UpdateModuleMapper(
+    PathRef Filename, const P1689Rule &Rule) {
+  ModulesDependencyNode *Node = Nodes[Filename].get();
+  assert(Node);
+
+  bool ModuleNameChanged = Rule.Provides
+                               ? (Node->Provided != Rule.Provides->ModuleName)
+                               : !Node->Provided;
+
+  if (ModuleNameChanged) {
+    for (auto *User : Node->Users)
+      User->Deps.erase(Node);
+
+    Node->Users.clear();
+  }
+
+  if (Node->Provided) {
+    llvm::StringRef OriginalModuleName = *Node->Provided;
+    assert(ModuleMapper.count(OriginalModuleName));
+    ModuleMapper.erase(OriginalModuleName);
+  }
+
+  if (!Rule.Provides)
+    return;
+
+  llvm::StringRef NewModuleName = Rule.Provides->ModuleName;
+  ModuleMapper.insert({NewModuleName, Node});
+}
+
+void clang::clangd::detail::ModulesDependencyGraph::UpdateSingleNode(
+    PathRef Filename, const P1689Rule &Rule, bool AllowInsertNewNode,
+    bool AllowUpdateModuleMapper, bool UpdateDependency) {
+  if (AllowInsertNewNode)
+    InsertNewNode(Filename);
+
+  if (AllowUpdateModuleMapper)
+    UpdateModuleMapper(Filename, Rule);
+
+  ModulesDependencyNode *UpdatingNode = Nodes[Filename].get();
+  assert(UpdatingNode);
+  bool DependencyChanged = UpdatingNode->UpdateProvidedAndRequires(Rule);
+  if (!UpdateDependency)
+    return;
+
+  UpdateDependencies({Filename}, DependencyChanged);
+}
+
+/// UpdateDependencies does 2 things:
+/// - Add edges to the dependency graph.
+/// - For all the changed files and the (transitively) users, reset their state
+/// of BMIPath.
+void clang::clangd::detail::ModulesDependencyGraph::UpdateDependencies(
+    const llvm::StringSet<> &Files, bool RecalculateEdges) {
+  if (RecalculateEdges)
+    for (const auto &FileIter : Files) {
+      llvm::StringRef File = FileIter.getKey();
+      ModulesDependencyNode *Node = Nodes[File].get();
+      assert(Node);
+
+      for (auto *Dep : Node->Deps)
+        Dep->Users.erase(Node);
+
+      Node->Deps.clear();
+
+      for (auto &Required : Node->Requires) {
+        llvm::StringRef RequiredModuleName = Required.getKey();
+
+        // It is possible that we're importing a third party module.
+        if (!ModuleMapper.count(RequiredModuleName))
+          continue;
+
+        ModulesDependencyNode *RequiredNode = ModuleMapper[RequiredModuleName];
+        Node->Deps.insert(RequiredNode);
+        RequiredNode->Users.insert(Node);
+      }
+    }
+
+  /// Reset the states of BMIPath.
+  llvm::SmallSetVector<StringRef, 32> Worklist;
+
+  // Due to the defect in llvm::StringSet, we can't use
+  //
+  //  Worklist(Files.begin(), Files.end());
+  //
+  // to initialize the worklist.
+  for (const auto &FileIter : Files)
+    Worklist.insert(FileIter.getKey());
+
+  // There shouldn't be circular modules dependency informations in a valid
+  // project. But we can't assume the project is valid.
+  llvm::StringSet<> NoDepCircleChecker;
+
+  while (!Worklist.empty()) {
+    llvm::StringRef Filename = Worklist.pop_back_val();
+    Nodes[Filename.str()]->BMIPath.reset();
+
+    if (NoDepCircleChecker.count(Filename)) {
+      elog("found circular modules dependency information in the project.");
+      break;
+    }
+
+    NoDepCircleChecker.insert(Filename);
+
+    for (auto *User : Nodes[Filename.str()]->Users)
+      if (Nodes[User->Name]->BMIPath)
+        Worklist.insert(User->Name);
+  }
+}
+
+bool ModulesManager::HasGraph() const {
+  auto _ = lockGraph();
+  return !Graph.empty();
+}
+
+bool ModulesManager::IsInGraph(PathRef Path) const {
+  auto _ = lockGraph();
+  return Graph.IsInGraph(Path);
+}
+
+bool ModulesManager::IsModuleInterface(PathRef Path) const {
+  auto _ = lockGraph();
+  return Graph.IsModuleInterface(Path);
+}
+
+std::string ModulesManager::GetModuleInterfaceName(PathRef Path) const {
+  auto _ = lockGraph();
+  return Graph.GetModuleInterfaceName(Path);
+}
+
+bool ModulesManager::IsReadyToCompile(PathRef Filename) const {
+  auto _ = lockGraph();
+  return Graph.IsReadyToCompile(Filename);
+}
+
+bool clang::clangd::detail::ModulesDependencyGraph::IsReadyToCompile(
+    PathRef Filename) const {
+  if (!Nodes.count(Filename))
+    return true;
+
+  auto *Node = Nodes.at(Filename).get();
+  return llvm::all_of(Node->Deps, [](auto *Dep) {
+    return Dep->BMIPath && !Dep->BMIPath->empty();
+  });
+}
+
+bool ModulesManager::HasInvalidDependencies(PathRef Filename) const {
+  auto _ = lockGraph();
+  return Graph.HasInvalidDependencies(Filename);
+}
+
+bool clang::clangd::detail::ModulesDependencyGraph::HasInvalidDependencies(
+    PathRef Filename) const {
+  if (!Nodes.count(Filename))
+    return true;
+
+  auto *Node = Nodes.at(Filename).get();
+  // It is ok to lookup for the direct dependencies since once a node has
+  // invalid BMI, all of its users will have invalid BMI.
+  return llvm::any_of(Node->Deps, [](auto *Dep) {
+    return Dep->BMIPath && Dep->BMIPath->empty();
+  });
+}
+
+namespace {
+llvm::SmallString<128> getAbsolutePath(const tooling::CompileCommand &Cmd) {
+  llvm::SmallString<128> AbsolutePath;
+  if (llvm::sys::path::is_absolute(Cmd.Filename)) {
+    AbsolutePath = Cmd.Filename;
+  } else {
+    AbsolutePath = Cmd.Directory;
+    llvm::sys::path::append(AbsolutePath, Cmd.Filename);
+    llvm::sys::path::remove_dots(AbsolutePath, true);
+  }
+  return AbsolutePath;
+}
+} // namespace
+
+void ModulesManager::addCallbackAfterReady(
+    PathRef Filename, std::function<void()> ReadyCallback,
+    std::function<void()> FailureCallback) {
+  std::lock_guard<std::mutex> Lock(WaitingCallablesMutex);
+  assert(!IsReadyToCompile(Filename));
+  assert(!HasInvalidDependencies(Filename));
+  if (FailureCallback)
+    WaitingCallables[Filename.str()].push_back(
+        {std::move(ReadyCallback), std::move(FailureCallback)});
+  else
+    WaitingCallables[Filename.str()].push_back(
+        {std::move(ReadyCallback), std::move(ReadyCallback)});
+}
+
+std::set<clang::clangd::detail::ModulesDependencyGraph::ModulesDependencyNode *>
+clang::clangd::detail::ModulesDependencyGraph::getAllUsers(
+    PathRef Filename) const {
+  std::set<ModulesDependencyNode *> Result;
+
+  llvm::SmallSetVector<ModulesDependencyNode *, 16> Worklist;
+  Worklist.insert(Nodes.at(Filename).get());
+
+  while (!Worklist.empty()) {
+    auto *Node = Worklist.pop_back_val();
+    assert(!Result.count(Node));
+    Result.insert(Node);
+
+    for (auto *User : Node->Users)
+      if (!Result.count(User))
+        Worklist.insert(User);
+  }
+
+  return Result;
+}
+
+void ModulesManager::setBMIPath(PathRef Filename, PathRef BMIPath) {
+  auto _ = lockGraph();
+  Graph.SetBMIPath(Filename, BMIPath);
+  bool Success = !BMIPath.empty();
+
+  for (auto *User :
+       Success ? Graph.getNodeUsers(Filename) : Graph.getAllUsers(Filename)) {
+    if (Success && !Graph.IsReadyToCompile(User->Name))
+      continue;
+
+    if (!Success)
+      Graph.SetBMIPath(User->Name, "");
+
+    std::lock_guard<std::mutex> Lock(WaitingCallablesMutex);
+    if (!WaitingCallables.count(User->Name))
+      continue;
+
+    for (const auto &[ReadyTask, FailureTask] : WaitingCallables[User->Name])
+      Runner.RunTask(Success ? std::move(ReadyTask) : std::move(FailureTask));
+
+    WaitingCallables[User->Name].clear();
+  }
+}
+
+void ModulesManager::GenerateModuleInterface(PathRef Path) {
+  /// Return an empty string implies that a compilation failure.
+  /// Return a string to the compiled module interface file.
+  auto GenerateInterfaceTask = [this](PathRef Path) -> std::string {
+    auto _ = llvm::make_scope_exit([this, Path] {
+      auto _ = lockGraph();
+      assert(ScheduledInterfaces.count(Path));
+      ScheduledInterfaces.erase(Path);
+    });
+
+    auto Cmd = CDB.getCompileCommand(tooling::getAbsolutePath(Path));
+    if (!Cmd) {
+      log("Failed to get the command for {0} when generating module interface",
+          Path);
+      return "";
+    }
+
+    ParseInputs Inputs;
+    Inputs.TFS = &CDB.getThreadsafeFS();
+    Inputs.CompileCommand = std::move(*Cmd);
+
+    IgnoreDiagnostics IgnoreDiags;
+    auto CI = buildCompilerInvocation(Inputs, IgnoreDiags);
+    if (!CI) {
+      log("Failed to build the compiler invocation for {0} when generating "
+          "module interface",
+          Path);
+      return "";
+    }
+
+    auto FS = Inputs.TFS->view(Inputs.CompileCommand.Directory);
+    auto AbsolutePath = getAbsolutePath(Inputs.CompileCommand);
+    auto Buf = FS->getBufferForFile(AbsolutePath);
+    if (!Buf)
+      return "";
+
+    log("Generating module file: {0}", Inputs.CompileCommand.Output);
+    CI->getFrontendOpts().OutputFile = Inputs.CompileCommand.Output;
+
+    auto Clang =
+        prepareCompilerInstance(std::move(CI), /*Preamble=*/nullptr,
+                                std::move(*Buf), std::move(FS), IgnoreDiags);
+    if (!Clang)
+      return "";
+
+    GenerateModuleInterfaceAction Action;
+    Clang->ExecuteAction(Action);
+
+    if (Clang->getDiagnostics().hasErrorOccurred())
+      return "";
+
+    return Inputs.CompileCommand.Output;
+  };
+
+  auto Task = [Path = Path.str(), this,
+               GenerateInterfaceTask = std::move(GenerateInterfaceTask)] {
+    {
+      auto _ = lockGraph();
+      assert(Graph.IsModuleInterface(Path));
+      if (ScheduledInterfaces.count(Path))
+        return;
+
+      ScheduledInterfaces.insert(Path);
+    }
+
+    setBMIPath(Path, GenerateInterfaceTask(Path));
+  };
+
+  assert(!HasInvalidDependencies(Path) &&
+         "It is meaningless to require to generate module interface if there "
+         "is invalid dependencies.");
+
+  if (!IsReadyToCompile(Path)) {
+    addCallbackAfterReady(Path, std::move(Task));
+    GenerateModuleInterfacesFor(Path);
+    return;
+  }
+
+  Runner.RunTask(std::move(Task));
+}
+
+void ModulesManager::GenerateModuleInterfacesFor(PathRef Path) {
+  // No graph implies that we're not in a modules repo.
+  if (!Graph.IsInGraph(Path))
+    return;
+
+  assert(!HasInvalidDependencies(Path) &&
+         "It is meaningless to require to generate module interface if there "
+         "is invalid dependencies.");
+
+  if (Graph.IsReadyToCompile(Path))
+    return;
+
+  llvm::SmallVector<std::string, 8> Names;
+  {
+    auto _ = lockGraph();
+    for (auto *Dep : Graph.getNode(Path)->Deps)
+      if (!Dep->BMIPath)
+        Names.push_back(Dep->Name);
+  }
+
+  for (const auto &Name : Names)
+    GenerateModuleInterface(Name);
+
+  return;
+}
+
+bool ModulesManager::IsDirectlyDependent(PathRef A, PathRef B) const {
+  auto _ = lockGraph();
+
+  auto *NodeA = Graph.getNode(A);
+  auto *NodeB = Graph.getNode(B);
+
+  assert(NodeA);
+  assert(NodeB);
+  assert(NodeB->Provided);
+
+  using namespace llvm;
+  return any_of(NodeA->Deps, [NodeA, NodeB](auto *Dep) {
+    // This is a little bit redudandant due to this is for testing.
+    return Dep == NodeB &&
+           any_of(NodeB->Users, [NodeA](auto *User) { return User == NodeA; });
+  });
+}
+
+size_t ModulesManager::GraphSize() const {
+  auto _ = lockGraph();
+  return Graph.size();
+}
+
+bool clang::clangd::detail::ModulesDependencyGraph::HasThirdpartyDependencies(
+    PathRef Path) const {
+  auto *Node = getNode(Path);
+
+  assert(Node);
+  assert(Node->Requires.size() >= Node->Users.size());
+
+  // This is redundant intentionally due to this function should be called
+  // in test.
+  bool Result = false;
+  for (const auto &Required : Node->Requires) {
+    llvm::StringRef RequiredModuleName = Required.getKey();
+
+    if (!ModuleMapper.count(RequiredModuleName)) {
+      Result = true;
+      continue;
+    }
+
+    // Test that the required node is in the deps.
+    auto *RequiredNode = ModuleMapper.at(RequiredModuleName);
+    assert(llvm::any_of(
+        Node->Deps, [RequiredNode](auto *Dep) { return RequiredNode == Dep; }));
+  }
+
+  return Result;
+}
+
+bool ModulesManager::HasThirdpartyDependencies(PathRef Path) const {
+  auto _ = lockGraph();
+  return Graph.HasThirdpartyDependencies(Path);
+}
+
+void clang::clangd::detail::ModulesTaskRunner::RunTask(
+    llvm::unique_function<void()> Task, const llvm::Twine &Name) {
+  if (Runner)
+    Runner->runAsync(
+        Name, [Task = std::move(Task), &Barrier = this->Barrier]() mutable {
+          std::unique_lock<Semaphore> Lock(Barrier, std::try_to_lock);
+          Task();
+        });
+  else
+    Task();
+}
+
+void clang::clangd::detail::ModulesTaskRunner::wait() {
+  if (Runner)
+    Runner->wait();
+}

clang-tools-extra/clangd/TUScheduler.h

void runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
                         llvm::unique_function<void()> Action, Semaphore &Sem);
 
   const GlobalCompilationDatabase &CDB;
   Options Opts;
   std::unique_ptr<ParsingCallbacks> Callbacks; // not nullptr
   Semaphore Barrier;
   Semaphore QuickRunBarrier;
   llvm::StringMap<std::unique_ptr<FileData>> Files;
+
   std::unique_ptr<ASTCache> IdleASTs;
   std::unique_ptr<HeaderIncluderCache> HeaderIncluders;
   // std::nullopt when running tasks synchronously and non-std::nullopt when
   // running tasks asynchronously.
   std::optional<AsyncTaskRunner> PreambleTasks;
   std::optional<AsyncTaskRunner> WorkerThreads;
   // Used to create contexts for operations that are not bound to a particular
   // file (e.g. index queries).
   std::string LastActiveFile;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/TUScheduler.cpp

 // requests will receive latest build preamble, which might possibly be stale.
 
 #include "TUScheduler.h"
 #include "CompileCommands.h"
 #include "Compiler.h"
 #include "Config.h"
 #include "Diagnostics.h"
 #include "GlobalCompilationDatabase.h"
+#include "ModulesManager.h"
 #include "ParsedAST.h"
 #include "Preamble.h"
 #include "index/CanonicalIncludes.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"
 #include "support/Logger.h"
 #include "support/MemoryTree.h"
 #include "support/Path.h"
public:
   /// accessed via getPossiblyStalePreamble(). Note that this function will
   /// return after an unsuccessful build of the preamble too, i.e. result of
   /// getPossiblyStalePreamble() can be null even after this function returns.
   void waitForFirstPreamble() const;
 
   TUScheduler::FileStats stats() const;
   bool isASTCached() const;
 
+  void waitForModulesBuilt() const;
+  void notifyModulesBuilt() const;
+
 private:
   // Details of an update request that are relevant to scheduling.
   struct UpdateType {
     // Do we want diagnostics from this version?
     // If Yes, we must always build this version.
     // If No, we only need to build this version if it's read.
     // If Auto, we build if it's read or if the debounce expires.
     WantDiagnostics Diagnostics;
private:
   // don't. When the old handle is destroyed, the old worker will stop reporting
   // any results to the user.
   bool CanPublishResults = true; /* GUARDED_BY(PublishMu) */
   std::atomic<unsigned> ASTBuildCount = {0};
   std::atomic<unsigned> PreambleBuildCount = {0};
 
   SynchronizedTUStatus Status;
   PreambleThread PreamblePeer;
+
+  mutable std::condition_variable ModulesCV;
+  // mutable std::condition_variable FileInputsCV;
+  // std::mutex InitMu;
 };
 
 /// A smart-pointer-like class that points to an active ASTWorker.
 /// In destructor, signals to the underlying ASTWorker that no new requests will
 /// be sent and the processing loop may exit (after running all pending
 /// requests).
 class ASTWorkerHandle {
   friend class ASTWorker;
assert(Requests.empty() && !CurrentRequest &&
          "unprocessed requests when destroying ASTWorker");
 #endif
 }
 
 void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags,
                        bool ContentChanged) {
   llvm::StringLiteral TaskName = "Update";
   auto Task = [=]() mutable {
+    if (auto *ModuleMgr = CDB.getModulesManager();
+        ModuleMgr && !ModuleMgr->IsReadyToCompile(FileName) &&
+        !ModuleMgr->HasInvalidDependencies(FileName)) {
+      log("{0} is not ready. wait for all the modules built.", FileName);
+
+      ModuleMgr->addCallbackAfterReady(FileName, [this]() {
+        log("{0} should be resumed", FileName);
+        notifyModulesBuilt();
+      });
+      ModuleMgr->GenerateModuleInterfacesFor(FileName);
+      waitForModulesBuilt();
+
+      log("{0} was resumed", FileName);
+    }
+
     // Get the actual command as `Inputs` does not have a command.
     // FIXME: some build systems like Bazel will take time to preparing
     // environment to build the file, it would be nice if we could emit a
     // "PreparingBuild" status to inform users, it is non-trivial given the
     // current implementation.
     auto Cmd = CDB.getCompileCommand(FileName);
     // If we don't have a reliable command for this file, it may be a header.
     // Try to find a file that includes it, to borrow its command.
void ASTWorker::runWithAST(
     llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
     TUScheduler::ASTActionInvalidation Invalidation) {
   // Tracks ast cache accesses for read operations.
   static constexpr trace::Metric ASTAccessForRead(
       "ast_access_read", trace::Metric::Counter, "result");
   auto Task = [=, Action = std::move(Action)]() mutable {
     if (auto Reason = isCancelled())
       return Action(llvm::make_error<CancelledError>(Reason));
+
     std::optional<std::unique_ptr<ParsedAST>> AST =
         IdleASTs.take(this, &ASTAccessForRead);
     if (!AST) {
       StoreDiags CompilerInvocationDiagConsumer;
       std::unique_ptr<CompilerInvocation> Invocation =
           buildCompilerInvocation(FileInputs, CompilerInvocationDiagConsumer);
       // Try rebuilding the AST.
       vlog("ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Name,
std::shared_ptr<const PreambleData> ASTWorker::getPossiblyStalePreamble(
   return LatestPreamble ? *LatestPreamble : nullptr;
 }
 
 void ASTWorker::waitForFirstPreamble() const {
   std::unique_lock<std::mutex> Lock(Mutex);
   PreambleCV.wait(Lock, [this] { return LatestPreamble || Done; });
 }
 
+void ASTWorker::waitForModulesBuilt() const {
+  auto *ModuleMgr = CDB.getModulesManager();
+  assert(ModuleMgr);
+  std::unique_lock<std::mutex> Lock(Mutex);
+  ModulesCV.wait(Lock, [ModuleMgr, this]() {
+    return ModuleMgr->IsReadyToCompile(FileName) ||
+           ModuleMgr->HasInvalidDependencies(FileName);
+  });
+}
+
+void ASTWorker::notifyModulesBuilt() const { ModulesCV.notify_all(); }
+
 tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
   std::unique_lock<std::mutex> Lock(Mutex);
   return FileInputs.CompileCommand;
 }
 
 TUScheduler::FileStats ASTWorker::stats() const {
   TUScheduler::FileStats Result;
   Result.ASTBuilds = ASTBuildCount;
ASTWorkerHandle Worker = ASTWorker::create(
         WorkerThreads ? &*WorkerThreads : nullptr, Barrier, Opts, *Callbacks);
     FD = std::unique_ptr<FileData>(
         new FileData{Inputs.Contents, std::move(Worker)});
     ContentChanged = true;
   } else if (FD->Contents != Inputs.Contents) {
     ContentChanged = true;
     FD->Contents = Inputs.Contents;
   }
+
+  if (auto *ModuleMgr = CDB.getModulesManager())
+    // TODO: Update all the nodes which are dependent on this.
+    ModuleMgr->UpdateNode(File.str());
+
   FD->Worker->update(std::move(Inputs), WantDiags, ContentChanged);
+
   // There might be synthetic update requests, don't change the LastActiveFile
   // in such cases.
   if (ContentChanged)
     LastActiveFile = File.str();
   return NewFile;
 }
 
 void TUScheduler::remove(PathRef File) {

clang-tools-extra/clangd/support/ThreadsafeFS.cpp

private:
     std::unique_ptr<File> Wrapped;
   };
 };
 } // namespace
 
 llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>
 ThreadsafeFS::view(PathRef CWD) const {
   auto FS = view(std::nullopt);
+  assert(FS);
   if (auto EC = FS->setCurrentWorkingDirectory(CWD))
     elog("VFS: failed to set CWD to {0}: {1}", CWD, EC.message());
   return FS;
 }
 
 llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>
 RealThreadsafeFS::viewImpl() const {
   // Avoid using memory-mapped files.
   // FIXME: Try to use a similar approach in Sema instead of relying on
   //        propagation of the 'isVolatile' flag through all layers.
   return new VolatileFileSystem(llvm::vfs::createPhysicalFileSystem());
 }
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/test/CMakeLists.txt

 set(CLANGD_TEST_DEPS
   clangd
   ClangdTests
   clangd-indexer
   # No tests for it, but we should still make sure they build.
   dexp
+  split-file
   )
 
 if(CLANGD_BUILD_XPC)
   list(APPEND CLANGD_TEST_DEPS clangd-xpc-test-client)
   list(APPEND CLANGD_TEST_DEPS ClangdXpcUnitTests)
 endif()
 
 if(CLANGD_ENABLE_REMOTE)

clang-tools-extra/clangd/test/modules.test

+# A smoke test to check the modules can work basically.
+#
+# RUN: rm -fr %t
+# RUN: mkdir -p %t
+# RUN: split-file %s %t
+#
+# RUN: sed -e "s|DIR|%/t|g" %t/compile_commands.json.tmpl > %t/compile_commands.json.tmp
+# RUN: sed -e "s|CLANG_CC|%clang|g" %t/compile_commands.json.tmp > %t/compile_commands.json
+# RUN: sed -e "s|DIR|%/t|g" %t/definition.jsonrpc.tmpl > %t/definition.jsonrpc
+#
+# RUN: clangd -experimental-modules-support -lit-test < %t/definition.jsonrpc \
+# RUN:      | FileCheck -strict-whitespace %t/definition.jsonrpc
+
+#--- A.cppm
+export module A;
+export void printA() {}
+
+#--- Use.cpp
+import A;
+void foo() {
+    print
+}
+
+#--- compile_commands.json.tmpl
+[
+    {
+      "directory": "DIR",
+      "command": "CLANG_CC -fprebuilt-module-path=DIR -std=c++20 -o DIR/main.cpp.o -c DIR/Use.cpp",
+      "file": "DIR/Use.cpp"
+    },
+    {
+      "directory": "DIR",
+      "command": "CLANG_CC -std=c++20 DIR/A.cppm --precompile -o DIR/A.pcm",
+      "file": "DIR/A.cppm"
+    }
+]
+
+#--- definition.jsonrpc.tmpl
+{
+  "jsonrpc": "2.0",
+  "id": 0,
+  "method": "initialize",
+  "params": {
+    "processId": 123,
+    "rootPath": "clangd",
+    "capabilities": {
+      "textDocument": {
+        "completion": {
+          "completionItem": {
+            "snippetSupport": true
+          }
+        }
+      }
+    },
+    "trace": "off"
+  }
+}
+---
+{
+  "jsonrpc": "2.0",
+  "method": "textDocument/didOpen",
+  "params": {
+    "textDocument": {
+      "uri": "file://DIR/Use.cpp",
+      "languageId": "cpp",
+      "version": 1,
+      "text": "import A;\nvoid foo() {\n    print\n}\n"
+    }
+  }
+}
+
+# CHECK: "message"{{.*}}printA{{.*}}(fix available)
+
+---
+{"jsonrpc":"2.0","id":1,"method":"textDocument/completion","params":{"textDocument":{"uri":"file://DIR/Use.cpp"},"context":{"triggerKind":1},"position":{"line":2,"character":6}}}
+---
+{"jsonrpc":"2.0","id":2,"method":"shutdown"}
+---
+{"jsonrpc":"2.0","method":"exit"}

clang-tools-extra/clangd/tool/ClangdMain.cpp

 // FIXME(kirillbobyrev): Should this be the location of compile_commands.json?
 opt<std::string> ProjectRoot{
     "project-root",
     cat(Features),
     desc("Path to the project root. Requires remote-index-address to be set."),
 };
 #endif
 
+opt<bool> ExperimentalModulesSupport{
+    "experimental-modules-support",
+    cat(Features),
+    desc("Experimental support for standard c++ modules"),
+    init(false),
+};
+
 /// Supports a test URI scheme with relaxed constraints for lit tests.
 /// The path in a test URI will be combined with a platform-specific fake
 /// directory to form an absolute path. For example, test:///a.cpp is resolved
 /// C:\clangd-test\a.cpp on Windows and /clangd-test/a.cpp on Unix.
 class TestScheme : public URIScheme {
 public:
   llvm::Expected<std::string>
   getAbsolutePath(llvm::StringRef /*Authority*/, llvm::StringRef Body,
#endif
   }
   for (int I = 0; I < argc; ++I)
     log("argv[{0}]: {1}", I, argv[I]);
   if (auto EnvFlags = llvm::sys::Process::GetEnv(FlagsEnvVar))
     log("{0}: {1}", FlagsEnvVar, *EnvFlags);
 
   ClangdLSPServer::Options Opts;
   Opts.UseDirBasedCDB = (CompileArgsFrom == FilesystemCompileArgs);
+  Opts.ExperimentalModulesSupport = ExperimentalModulesSupport;
 
   switch (PCHStorage) {
   case PCHStorageFlag::Memory:
     Opts.StorePreamblesInMemory = true;
     break;
   case PCHStorageFlag::Disk:
     Opts.StorePreamblesInMemory = false;
     break;

clang-tools-extra/clangd/unittests/CMakeLists.txt

add_unittest(ClangdUnitTests ClangdTests
   IndexActionTests.cpp
   IndexTests.cpp
   InlayHintTests.cpp
   InsertionPointTests.cpp
   JSONTransportTests.cpp
   LoggerTests.cpp
   LSPBinderTests.cpp
   LSPClient.cpp
+  ModulesManagerTests.cpp
   ModulesTests.cpp
   ParsedASTTests.cpp
   PathMappingTests.cpp
   PreambleTests.cpp
   PrintASTTests.cpp
   ProjectAwareIndexTests.cpp
   QualityTests.cpp
   RIFFTests.cpp

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

+//===-- ModulesManagerTests.cpp ---------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Config.h"
+#include "ModulesManager.h"
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using namespace clang;
+using namespace clang::clangd;
+using namespace llvm;
+
+namespace {
+class ModulesManagerTest : public ::testing::Test {
+  void SetUp() override {
+    ASSERT_FALSE(sys::fs::createUniqueDirectory("modules-test", TestDir));
+    llvm::errs() << "Created TestDir: " << TestDir << "\n";
+  }
+
+  void TearDown() override {
+    // sys::fs::remove_directories(TestDir);
+  }
+
+public:
+  SmallString<256> TestDir;
+
+  // Add files to the working testing directory and repalce all the
+  // `__DIR__` to TestDir.
+  void addFile(StringRef Path, StringRef Contents) {
+    ASSERT_FALSE(sys::path::is_absolute(Path));
+
+    SmallString<256> AbsPath(TestDir);
+    sys::path::append(AbsPath, Path);
+
+    ASSERT_FALSE(
+        sys::fs::create_directories(llvm::sys::path::parent_path(AbsPath)));
+
+    std::error_code EC;
+    llvm::raw_fd_ostream OS(AbsPath, EC);
+    ASSERT_FALSE(EC);
+
+    std::size_t Pos = Contents.find("__DIR__");
+    while (Pos != llvm::StringRef::npos) {
+      OS << Contents.take_front(Pos);
+      OS << TestDir;
+      Contents = Contents.drop_front(Pos + sizeof("__DIR__") - 1);
+      Pos = Contents.find("__DIR__");
+    }
+
+    OS << Contents;
+  }
+
+  // Get the absolute path for file specified by Path under testing working
+  // directory.
+  std::string getFullPath(StringRef Path) {
+    SmallString<128> Result(TestDir);
+    sys::path::append(Result, Path);
+    return Result.str().str();
+  }
+};
+
+TEST_F(ModulesManagerTest, ReplaceCommandsTest) {
+  addFile("build/compile_commands.json", R"cpp(
+[
+{
+  "directory": "__DIR__",
+  "command": "clang++ -std=c++20 __DIR__/M.cppm -c -o __DIR__/M.o -fmodule-file=D=__DIR__/D.pcm",
+  "file": "__DIR__/M.cppm",
+  "output": "__DIR__/M.o"
+}
+]
+  )cpp");
+
+  addFile("M.cppm", R"cpp(
+export module M;
+import D;
+  )cpp");
+
+  RealThreadsafeFS TFS;
+  DirectoryBasedGlobalCompilationDatabase::Options Opts(TFS);
+  DirectoryBasedModulesGlobalCompilationDatabase MCDB(Opts,
+                                                      /*AsyncThreadsCount*/ 4);
+
+  std::optional<tooling::CompileCommand> Cmd =
+      MCDB.getCompileCommand(getFullPath("M.cppm"));
+  EXPECT_TRUE(Cmd);
+  // Since the graph is not built yet. We don't expect to see the mutated
+  // command line for modules.
+  EXPECT_FALSE(any_of(Cmd->CommandLine, [](StringRef Arg) {
+    return Arg.count("-fprebuilt-module-path");
+  }));
+  EXPECT_TRUE(any_of(Cmd->CommandLine, [](StringRef Arg) {
+    return Arg.count("-fmodule-file=");
+  }));
+
+  ModulesManager *MMgr = MCDB.getModulesManager();
+  EXPECT_TRUE(MMgr);
+  MMgr->UpdateNode(getFullPath("M.cppm"));
+
+  MMgr->waitUntilInitialized();
+
+  Cmd = MCDB.getCompileCommand(getFullPath("M.cppm"));
+  EXPECT_TRUE(Cmd);
+  // Since the graph has been built. We expect to see the mutated command line
+  // for modules.
+  EXPECT_TRUE(any_of(Cmd->CommandLine, [](StringRef Arg) {
+    return Arg.count("-fprebuilt-module-path");
+  }));
+  EXPECT_FALSE(any_of(Cmd->CommandLine, [](StringRef Arg) {
+    return Arg.count("-fmodule-file=");
+  }));
+}
+
+void AddHelloWorldExample(ModulesManagerTest *Test) {
+  assert(Test);
+
+  Test->addFile("build/compile_commands.json", R"cpp(
+[
+{
+  "directory": "__DIR__",
+  "command": "clang++ -std=c++20 __DIR__/M.cppm -c -o __DIR__/M.o",
+  "file": "__DIR__/M.cppm",
+  "output": "__DIR__/M.o"
+},
+{
+  "directory": "__DIR__",
+  "command": "clang++ -std=c++20 __DIR__/Impl.cpp -c -o __DIR__/Impl.o",
+  "file": "__DIR__/Impl.cpp",
+  "output": "__DIR__/Impl.o"
+},
+{
+  "directory": "__DIR__",
+  "command": "clang++ -std=c++20 __DIR__/impl_part.cppm -c -o __DIR__/impl_part.o",
+  "file": "__DIR__/impl_part.cppm",
+  "output": "__DIR__/impl_part.o"
+},
+{
+  "directory": "__DIR__",
+  "command": "clang++ -std=c++20 __DIR__/interface_part.cppm -c -o __DIR__/interface_part.o",
+  "file": "__DIR__/interface_part.cppm",
+  "output": "__DIR__/interface_part.o"
+},
+{
+  "directory": "__DIR__",
+  "command": "clang++ -std=c++20 __DIR__/User.cpp -c -o __DIR__/User.o",
+  "file": "__DIR__/User.cpp",
+  "output": "__DIR__/User.o"
+}
+]
+)cpp");
+
+  Test->addFile("M.cppm", R"cpp(
+export module M;
+export import :interface_part;
+import :impl_part;
+export void Hello();
+  )cpp");
+
+  Test->addFile("Impl.cpp", R"cpp(
+module;
+#include "header.mock"
+module M;
+void Hello() {
+}
+  )cpp");
+
+  Test->addFile("impl_part.cppm", R"cpp(
+module;
+#include "header.mock"
+module M:impl_part;
+import :interface_part;
+
+void World() {
+    
+}
+  )cpp");
+
+  Test->addFile("header.mock", "");
+
+  Test->addFile("interface_part.cppm", R"cpp(
+export module M:interface_part;
+export void World();
+  )cpp");
+
+  Test->addFile("User.cpp", R"cpp(
+import M;
+import third_party_module;
+int main() {
+    Hello();
+    World();
+    return 0;
+}
+  )cpp");
+}
+
+TEST_F(ModulesManagerTest, BuildGraphTest) {
+  AddHelloWorldExample(this);
+
+  RealThreadsafeFS TFS;
+  DirectoryBasedGlobalCompilationDatabase::Options Opts(TFS);
+  DirectoryBasedModulesGlobalCompilationDatabase MCDB(Opts,
+                                                      /*AsyncThreadsCount*/ 4);
+
+  ModulesManager *MMgr = MCDB.getModulesManager();
+  EXPECT_TRUE(MMgr);
+  EXPECT_FALSE(MMgr->HasGraph());
+  MMgr->UpdateNode(getFullPath("M.cppm"));
+
+  MMgr->waitUntilInitialized();
+
+  EXPECT_TRUE(MMgr->HasGraph());
+  EXPECT_EQ(MMgr->GraphSize(), 5u);
+  EXPECT_TRUE(MMgr->IsDirectlyDependent(getFullPath("M.cppm"),
+                                        getFullPath("impl_part.cppm")));
+  EXPECT_TRUE(MMgr->IsDirectlyDependent(getFullPath("M.cppm"),
+                                        getFullPath("interface_part.cppm")));
+  EXPECT_TRUE(MMgr->IsDirectlyDependent(getFullPath("impl_part.cppm"),
+                                        getFullPath("interface_part.cppm")));
+  EXPECT_TRUE(MMgr->IsDirectlyDependent(getFullPath("Impl.cpp"),
+                                        getFullPath("M.cppm")));
+  EXPECT_TRUE(MMgr->IsDirectlyDependent(getFullPath("User.cpp"),
+                                        getFullPath("M.cppm")));
+  EXPECT_TRUE(MMgr->HasThirdpartyDependencies(getFullPath("User.cpp")));
+}
+
+TEST_F(ModulesManagerTest, GenerateModuleInterfaceAndUpdateTest) {
+  AddHelloWorldExample(this);
+
+  RealThreadsafeFS TFS;
+  DirectoryBasedGlobalCompilationDatabase::Options Opts(TFS);
+  Opts.CompileCommandsDir = getFullPath("build");
+  DirectoryBasedModulesGlobalCompilationDatabase MCDB(Opts,
+                                                      /*AsyncThreadsCount*/ 4);
+
+  ModulesManager *MMgr = MCDB.getModulesManager();
+  EXPECT_TRUE(MMgr);
+
+  MMgr->UpdateNode(getFullPath("M.cppm"));
+
+  MMgr->waitUntilInitialized();
+
+  EXPECT_FALSE(MMgr->IsReadyToCompile(getFullPath("User.cpp")));
+
+  std::condition_variable ReadyCompileCV;
+
+  MMgr->addCallbackAfterReady(getFullPath("User.cpp"), [&ReadyCompileCV]() {
+    ReadyCompileCV.notify_all();
+  });
+  MMgr->GenerateModuleInterfacesFor(getFullPath("User.cpp"));
+
+  std::mutex Mu;
+  std::unique_lock<std::mutex> Lock(Mu);
+  ReadyCompileCV.wait(Lock, [MMgr, this]() {
+    return MMgr->IsReadyToCompile(getFullPath("User.cpp"));
+  });
+
+  EXPECT_TRUE(MMgr->IsReadyToCompile(getFullPath("User.cpp")));
+  EXPECT_TRUE(
+      sys::fs::exists(getFullPath("build/.cache/clangd/module_files/M.pcm")));
+  EXPECT_TRUE(sys::fs::exists(
+      getFullPath("build/.cache/clangd/module_files/M-impl_part.pcm")));
+  EXPECT_TRUE(sys::fs::exists(
+      getFullPath("build/.cache/clangd/module_files/M-interface_part.pcm")));
+
+  MMgr->UpdateNode(getFullPath("User.cpp"));
+  EXPECT_TRUE(MMgr->IsReadyToCompile(getFullPath("User.cpp")));
+
+  MMgr->UpdateNode(getFullPath("Impl.cpp"));
+  EXPECT_TRUE(MMgr->IsReadyToCompile(getFullPath("User.cpp")));
+
+  MMgr->UpdateNode(getFullPath("M.cppm"));
+  EXPECT_FALSE(MMgr->IsReadyToCompile(getFullPath("User.cpp")));
+}
+
+TEST_F(ModulesManagerTest, InvalidBMITest) {
+  addFile("build/compile_commands.json", R"cpp(
+[
+{
+  "directory": "__DIR__",
+  "command": "clang++ -std=c++20 __DIR__/M.cppm -c -o __DIR__/M.o",
+  "file": "__DIR__/M.cppm",
+  "output": "__DIR__/M.o"
+},
+{
+  "directory": "__DIR__",
+  "command": "clang++ -std=c++20 __DIR__/User.cpp -c -o __DIR__/User.o",
+  "file": "__DIR__/User.cpp",
+  "output": "__DIR__/User.o"
+}
+]
+  )cpp");
+
+  addFile("M.cppm", R"cpp(
+export module M;
+export void Func() {
+  wlajdliajlwdjawdjlaw // invalid program
+}
+  )cpp");
+
+  addFile("User.cpp", R"cpp(
+import M;
+void foo() {
+  Func();
+}
+  )cpp");
+
+  RealThreadsafeFS TFS;
+  DirectoryBasedGlobalCompilationDatabase::Options Opts(TFS);
+  DirectoryBasedModulesGlobalCompilationDatabase MCDB(Opts,
+                                                      /*AsyncThreadsCount*/ 4);
+  ModulesManager *MMgr = MCDB.getModulesManager();
+  EXPECT_TRUE(MMgr);
+  MMgr->UpdateNode(getFullPath("User.cpp"));
+  MMgr->waitUntilInitialized();
+
+  EXPECT_FALSE(MMgr->IsReadyToCompile(getFullPath("User.cpp")));
+  EXPECT_FALSE(MMgr->HasInvalidDependencies(getFullPath("User.cpp")));
+
+  std::condition_variable ReadyCompileCV;
+  bool Failed = false;
+
+  MMgr->addCallbackAfterReady(
+      getFullPath("User.cpp"),
+      /*ReadyCallback*/ [&ReadyCompileCV]() { ReadyCompileCV.notify_all(); },
+      /*Failed Callback*/
+      [&ReadyCompileCV, &Failed]() {
+        ReadyCompileCV.notify_all();
+        Failed = true;
+      });
+  MMgr->GenerateModuleInterfacesFor(getFullPath("User.cpp"));
+
+  std::mutex Mu;
+  std::unique_lock<std::mutex> Lock(Mu);
+  ReadyCompileCV.wait(Lock, [MMgr, this]() {
+    return MMgr->HasInvalidDependencies(getFullPath("User.cpp"));
+  });
+
+  EXPECT_TRUE(MMgr->HasInvalidDependencies(getFullPath("User.cpp")));
+  // Make sure that the failure callback are called.
+  EXPECT_TRUE(Failed);
+}
+
+} // anonymous namespace

clang-tools-extra/docs/ReleaseNotes.rst

 Major New Features
 ------------------
 
 ...
 
 Improvements to clangd
 ----------------------
 
+- Implemented the experimental support for C++20 modules. This can be enabled by
+  `-experimental-modules-support` option.
+
 Inlay hints
 ^^^^^^^^^^^
 
 Diagnostics
 ^^^^^^^^^^^
 
 Semantic Highlighting
 ^^^^^^^^^^^^^^^^^^^^^