This is an archive of the discontinued LLVM Phabricator instance.

[llvm] Remove dependency on <algorithm> [NFC]
AbandonedPublic

Authored by mgrang on Jan 23 2019, 12:39 PM.

Details

Summary

algorithm was mainly included for std::sort. Now that we have replaced std::sort with llvm::sort we no longer need algorithm.

Diff Detail

Event Timeline

mgrang created this revision.Jan 23 2019, 12:39 PM

"mainly" used for std::sort might be true, but "only" used might be harder to prove - did you use any tooling to test that these inclusions weren't needed other than "this code still compiles" (which has the problem that the inclusion might be used, but also included indirectly from some other header - so removing it may still compile, but introduces an undesirable indirect dependency on an implementation detail of some other header)

"mainly" used for std::sort might be true, but "only" used might be harder to prove - did you use any tooling to test that these inclusions weren't needed other than "this code still compiles" (which has the problem that the inclusion might be used, but also included indirectly from some other header - so removing it may still compile, but introduces an undesirable indirect dependency on an implementation detail of some other header)

I ran ninja check-all and did not see any failures. I haven't changed the places where algorithm is needed (like for std::fill, etc) and which introduced compile errors. I have also not touched examples, unittests and util/unittest directories.

"mainly" used for std::sort might be true, but "only" used might be harder to prove - did you use any tooling to test that these inclusions weren't needed other than "this code still compiles" (which has the problem that the inclusion might be used, but also included indirectly from some other header - so removing it may still compile, but introduces an undesirable indirect dependency on an implementation detail of some other header)

I ran ninja check-all and did not see any failures. I haven't changed the places where algorithm is needed (like for std::fill, etc) and which introduced compile errors. I have also not touched examples, unittests and util/unittest directories.

How did you identify these "I haven't changed the places where algorithm is needed (like for std::fill, etc)" places? By visual inspection of every file that's been touched?

"mainly" used for std::sort might be true, but "only" used might be harder to prove - did you use any tooling to test that these inclusions weren't needed other than "this code still compiles" (which has the problem that the inclusion might be used, but also included indirectly from some other header - so removing it may still compile, but introduces an undesirable indirect dependency on an implementation detail of some other header)

I ran ninja check-all and did not see any failures. I haven't changed the places where algorithm is needed (like for std::fill, etc) and which introduced compile errors. I have also not touched examples, unittests and util/unittest directories.

How did you identify these "I haven't changed the places where algorithm is needed (like for std::fill, etc)" places? By visual inspection of every file that's been touched?

No, I removed the header from all files and then put back only where the compilation failed. I agree with your comment "removing it may still compile, but introduces an undesirable indirect dependency on an implementation detail of some other header". I guess there is no foolproof way to rule out *any* possible use of the header?

"mainly" used for std::sort might be true, but "only" used might be harder to prove - did you use any tooling to test that these inclusions weren't needed other than "this code still compiles" (which has the problem that the inclusion might be used, but also included indirectly from some other header - so removing it may still compile, but introduces an undesirable indirect dependency on an implementation detail of some other header)

I ran ninja check-all and did not see any failures. I haven't changed the places where algorithm is needed (like for std::fill, etc) and which introduced compile errors. I have also not touched examples, unittests and util/unittest directories.

How did you identify these "I haven't changed the places where algorithm is needed (like for std::fill, etc)" places? By visual inspection of every file that's been touched?

No, I removed the header from all files and then put back only where the compilation failed. I agree with your comment "removing it may still compile, but introduces an undesirable indirect dependency on an implementation detail of some other header".

Yeah, I don't think it's probably the best thing to commit a change like that for this header or any other (you can imagine how brittle the codebase might become if we did this for all headers)

I guess there is no foolproof way to rule out *any* possible use of the header?

There are some tools - IWYU was an old one that had some issues, but made some effort to get this right ( https://include-what-you-use.org/ ) and I don't know if any clang tools (clang-tidy or the like) have grown a better implementation of that functionality yet.

@mgrang Which compilers/oses have you tested in your ninja build? asserts? EXPENSIVE_CHECKS?

rupprecht requested changes to this revision.Jan 23 2019, 1:40 PM

I just took a look at the file Herald added me for (tools/llvm-objcopy/llvm-objcopy.cpp), and it uses std::copy from <algorithm>. I imagine many of the files in this patch are similar.

Arbitrarily removing includes like this just makes things fragile -- things will start breaking when an include is removed from a completely unrelated header. An iwyu-based approach would be better for this kind of patch -- which still requires taking care as it could create some breakages, but in a much less fragile way.

This revision now requires changes to proceed.Jan 23 2019, 1:40 PM

@mgrang Which compilers/oses have you tested in your ninja build? asserts? EXPENSIVE_CHECKS?

I tested my +asserts build on Ubuntu Linux.

mgrang added a comment.EditedJan 24 2019, 11:03 AM

I wanted to clean up the inclusions of algorithm due to std::sort. But seems like this change may potentially break some things. So for now we can let it pass? (Meaning I can abandon this patch).

I wanted to clean up the inclusions of algorithm due to std::sort. But seems like this change may potentially break some things. So for now we can let it pass? (Meaning I can abandon this patch).

Yep - thanks for trying, but unless you can get something like IWYU working to help ensure this cleanup is a bit more robust - I'd probably suggest just abandoning this change, unfortunately.

mgrang abandoned this revision.Jan 24 2019, 11:17 AM

I wanted to clean up the inclusions of algorithm due to std::sort. But seems like this change may potentially break some things. So for now we can let it pass? (Meaning I can abandon this patch).

Yep - thanks for trying, but unless you can get something like IWYU working to help ensure this cleanup is a bit more robust - I'd probably suggest just abandoning this change, unfortunately.

Thanks a lot David. I will definitely try IWYU when I have time. Abandoning this patch now.