This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][gardening] Move all algorithms into their own headers.
ClosedPublic

Authored by ldionne on Jun 2 2021, 6:18 PM.

Details

Summary

This is a fairly mechanical change, it just moves each algorithm into its own header. This is a NFC.

Note: during this change, I burned down all the includes, so this follows "include only and exactly what you use."

There may be some module work that needs to happen here. Let's see what the CI thinks.

Diff Detail

Event Timeline

zoecarver created this revision.Jun 2 2021, 6:18 PM
zoecarver requested review of this revision.Jun 2 2021, 6:18 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript

Note: this change includes D103330. I just subsumed that patch because I need to use some things form it and update it a bit. I think it's easiest to just take this one rather than trying to deal with merge conflicts and updates to that one.

zoecarver updated this revision to Diff 349440.Jun 2 2021, 6:22 PM

Remove two unrelated files.

cjdb added inline comments.Jun 2 2021, 8:25 PM
libcxx/include/module.modulemap
220–223

You'll need to replicate what I do in D103551 for every algorithm header.

395–396
437–440

Delete.

537–540

Delete.

Not a blocker, but just for curiosity's sake, could you run graph_header_deps.py before and after this patch and upload the images somewhere?
libcxx/utils/graph_header_deps.py | dot -Tpng > coolgraph.png
We expect the graph to get vastly more dotty-and-liney, but maybe less bottlenecky? It'd be interesting to look at, anyway.

ldionne accepted this revision.Jun 3 2021, 7:30 AM

This LGTM, however I want to understand the recent Modules failures better before checking this in, to make sure we don't have to revert it. It has the potential to be fairly disruptive (in terms of downstream merge conflicts for people with forks and stuff like that). I just want to make sure that we get it right the first time around, so please hold on with committing until we've made sure of that.

This revision is now accepted and ready to land.Jun 3 2021, 7:30 AM
cjdb requested changes to this revision.Jun 3 2021, 10:19 AM

Note: during this change, I burned down all the includes, so this follows "include only and exactly what you use."

In D103330 @ldionne asked that this be done in a separate patch.

This revision now requires changes to proceed.Jun 3 2021, 10:19 AM
libcxx/include/algorithm
648–665

(A) Why are these few headers alphabetized and then the bulk of them (below) done... below?

(B) @cjdb wrote:

Note: during this change, I burned down all the includes, so this follows "include only and exactly what you use."

In D103330 @ldionne asked that this be done in a separate patch.

The important thing @ldionne was getting at in D103330 is Hyrum's Law. We need to make sure that we don't break any of libc++'s customers who might be relying on the fact e.g. "by including <algorithm>, I also receive all of <functional>." @zoecarver's change doesn't actually affect those customers AFAICT, because he's leaving the existing includes alone here (e.g. <algorithm> does still include <functional>).

However, @zoecarver, please do triple-check this PR to make sure that the top-level <algorithm> header still includes all the facilities it used to, and that the same is true for all other top-level publicly visible headers (e.g. <functional>, <iterator>, anything else that might have changed).

zoecarver updated this revision to Diff 349609.Jun 3 2021, 10:55 AM
  • Modularize
zoecarver added inline comments.Jun 3 2021, 10:58 AM
libcxx/include/algorithm
648–665

(A) Why are these few headers alphabetized and then the bulk of them (below) done... below?

Arg. Sorry this came out of merging Chris' patch with mine. Will fix. (Come to think of it, I also need to update the cmake list.)

The important thing @ldionne was getting at in D103330 is Hyrum's Law. We need to make sure that we don't break any of libc++'s customers who might be relying on the fact e.g. "by including <algorithm>, I also receive all of <functional>." @zoecarver's change doesn't actually affect those customers AFAICT, because he's leaving the existing includes alone here (e.g. <algorithm> does still include <functional>).

However, @zoecarver, please do triple-check this PR to make sure that the top-level <algorithm> header still includes all the facilities it used to, and that the same is true for all other top-level publicly visible headers (e.g. <functional>, <iterator>, anything else that might have changed).

Yes. I haven't removed anything from <algorithm>.

zoecarver updated this revision to Diff 349613.Jun 3 2021, 11:13 AM
  • Re-alphabatize and add a few missing modules to the module map
  • __search.h -> search.h
zoecarver updated this revision to Diff 349614.Jun 3 2021, 11:14 AM
  • Remove two unrealted files
cjdb accepted this revision.Jun 3 2021, 11:23 AM

LGTM pending my requested deletions.

libcxx/include/module.modulemap
292–294

Delete

This revision is now accepted and ready to land.Jun 3 2021, 11:23 AM
zoecarver updated this revision to Diff 349628.Jun 3 2021, 11:49 AM

Add back half_positive.h which got removed on accident (and I didn't catch it because cmake cached it in the build directoyr).

zoecarver updated this revision to Diff 349662.Jun 3 2021, 12:54 PM

Fix another include issue that I didn't catch thanks to ninja caching.

Double-check your module.modulemap changes: I still see at least one export * in there.
Also some removed blank lines that may or may not have been on purpose. Just make sure the style we end up with is consistent across all the sections of module.modulemap.
Otherwise, sure, LGTM (modulo my usual curmudgeoning that all these little headers are gonna be icky).

Also: I assume it's intentional that you went with half_positive.h instead of __half_positive.h, and so on? (I.e., some of these files define standard algorithms and some define helpers, with no clear naming distinction between the two kinds.)

cjdb added a comment.Jun 3 2021, 2:37 PM

Also: I assume it's intentional that you went with half_positive.h instead of __half_positive.h, and so on? (I.e., some of these files define standard algorithms and some define helpers, with no clear naming distinction between the two kinds.)

Agreed that we should probably get a convention going. We can do that offline, but I've been following whatever is the salient feature of the file. If it's __half_positive, then I'd make the header __half_positive.h.

libcxx/include/module.modulemap
295

This export * still needs to go.

ldionne reopened this revision.Jun 17 2021, 8:49 AM
This revision is now accepted and ready to land.Jun 17 2021, 8:49 AM
ldionne commandeered this revision.Jun 17 2021, 9:15 AM
ldionne edited reviewers, added: zoecarver; removed: ldionne.

Commandeering as I'm getting ready to re-apply this change (well, really D104171 which is a mix of D103330, this and additional work).

ldionne added a subscriber: phosek.

@phosek Could you please apply this change locally and run whatever you ran that caused you to revert last week? I think we should have fixed our stuff, but I really want to make sure we're not going to break you again, because it's extremely painful for us to revert and re-apply such a large change (and it messes up the history pretty badly, too).

This revision now requires review to proceed.Jun 17 2021, 9:18 AM
phosek accepted this revision.Jun 18 2021, 7:16 PM

LGTM

This revision is now accepted and ready to land.Jun 18 2021, 7:16 PM
This revision was automatically updated to reflect the committed changes.