Page MenuHomePhabricator

[libcxx][algorithms] adds ranges::is_partitioned and ranges::partition_point
Needs ReviewPublic

Authored by cjdb on Jul 12 2021, 12:14 AM.

Details

Reviewers
ldionne
zoecarver
Mordante
EricWF
Group Reviewers
Restricted Project
Summary

Implements part of http://wg21.link/P0896.
Implements part of [alg.partitions].

Depends on D105793.

Diff Detail

Event Timeline

cjdb requested review of this revision.Jul 12 2021, 12:14 AM
cjdb created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptJul 12 2021, 12:14 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
cjdb updated this revision to Diff 358152.Jul 12 2021, 10:10 PM

rebases to activate CI

cjdb updated this revision to Diff 358304.Jul 13 2021, 9:27 AM

rebases to activate CI

cjdb updated this revision to Diff 358374.Jul 13 2021, 11:39 AM

rebases to activate CI

cjdb updated this revision to Diff 359371.Jul 16 2021, 9:56 AM

rebases to activate CI

I didn't do a detailed analysis of the algorithm used.

libcxx/include/__algorithm/is_partitioned.h
52

Please add _LIBCPP_TEMPLATE_VIS and validate all other structs.

57

Please add _LIBCPP_HIDE_FROM_ABI and check all other functions.

68

__last is used after moving.

libcxx/include/__algorithm/partition_point.h
71

Why the const in const _Sp __last. (I personally like it, but it deviates from our coding style.)

libcxx/include/algorithm
369

Please add // since C++20 to these two.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp
44

Can the range move to the parent scope?

46

Why can't you test against an exact value?

cjdb added a comment.Jul 21 2021, 10:31 AM

I didn't do a detailed analysis of the algorithm used.

Thanks for the review! A few clarifying things, but this all sounds reasonable.

libcxx/include/__algorithm/partition_point.h
71

I like the compiler catching accidental writes. Also, this is a new section of code, so I think it's worth piloting this style here. (@ldionne seems to be ambivalent towards it based on prior commits as evidence.)

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp
44

Yes, it can. I think this is a relic of when range used complexity_iterator (where the answer would've been "no").

46

I guess it's possible to say pred.count() <= 5, but my interpretation of the wording at the time made me want to base this in terms of the range's length. I take it you'd prefer 5 over ssize(all_odd)?

Mordante added inline comments.Jul 23 2021, 3:00 AM
libcxx/include/__algorithm/partition_point.h
71

I like the const too for the the same reason. So then let's keep it. I probably will start to use it in new code too.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp
46

No I like the ssize(all_odd) over 5. IMO 5 is a fragile magic number.
I see I misread the test. It tests the complexity of the algorithm.
IMO it would be clearer to use assert(pred.count() <= ranges::ssize(range));

So just discard my previous comment.

Quuxplusone added inline comments.
libcxx/include/__algorithm/partition_point.h
71

@cjdb @Mordante @ldionne: Please, please, don't misuse const to "pass by const value" or "return by const value." These are common typos in C++ code. @zoecarver will (I hope) recall the couple of times I've caught bugs in his code by grepping for pass-by-const-value typos.

I have a whole blog post on "const" here:
https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/

and it ends with [a set of git grep regexes](https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/#grep-your-codebase-today) that enable anyone — not just me, but any of you! — to find your missing-ampersand typos by grepping for parameters of the form const _Sp __last. If you start using that typo-style in code you don't want to change, it makes the job of the typo-finder vastly harder.

As of this writing, we have only five instances of pass-by-const-value in the codebase. Three of them are in requires-clauses.

$ git grep '[(,] *const [A-Za-z0-9_:]* [A-Za-z0-9_:]* *[,)=]'
__iterator/advance.h:      if (const auto __M = __bound - __i; __abs(__n) >= __abs(__M)) {
__iterator/concepts.h:  requires(const _In __i) {
__iterator/concepts.h:  requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {
__iterator/iter_swap.h:  requires(const _I1 __i1, const _I2 __i2) {
random:binomial_distribution<_IntType>::param_type::param_type(const result_type __t, const double __p)
cjdb marked 2 inline comments as done.Jul 23 2021, 9:41 AM
cjdb added inline comments.
libcxx/include/__algorithm/partition_point.h
71

I've read through this a handful of times now. I don't find it particularly convincing. You claim that they're "common typos", but I can only find one concrete example that you've come across in that blog, which doesn't generalise. I can't speak to Zoe's experience here.

Yes, const-qualifying value parameters can be a problem. It's not absolute truth that they all are. You wrote that "const is a contract". I agree with this: hell, I even teach it, but it seems we have a fundamental point of contention on this topic. Your blog implies that it's only a contract between a programmer and the interface they're programming against. From this perspective, yes, a const value parameter is useless, but this is not the only way in which const is a contract. const is also a contract between the programmer and the compiler. Under this lens, a const value parameter has strong meaning, because it gives both the reader and writer strong confidence that the object isn't going to be modified.

and it ends with a set of git grep regexes that enable anyone — not just me, but any of you! — to find your missing-ampersand typos by grepping for parameters of the form const _Sp __last. If you start using that typo-style in code you don't want to change, it makes the job of the typo-finder vastly harder.

This isn't as strong an argument against const value parameters as you think it is. It effectively reads as "let's weaken our code guarantees so that the person auditing our codebase has an easy time doing their audit". If you want an effective and painless auditing experience, write a tool that automates the process and has a configurable set of exemptions or set of rules.

79

Needs to be std::iter_difference_t<_Ip>{0}.

Mordante added inline comments.Jul 25 2021, 8:01 AM
libcxx/include/__algorithm/partition_point.h
71

and it ends with [a set of git grep regexes](https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/#grep-your-codebase-today) that enable anyone — not just me, but any of you! — to find your missing-ampersand typos by grepping for parameters of the form const _Sp __last. If you start using that typo-style in code you don't want to change, it makes the job of the typo-finder vastly harder.

I love grep, but IMO grep isn't the best tool for this job. Nowadays there are more powerful tools for this job. For example, clang-tidy has performance-unnecessary-value-param https://clang.llvm.org/extra/clang-tidy/checks/performance-unnecessary-value-param.html .

So if we have errors due to incorrect usage of const I'd much rather invest time to improve our tooling to catch these errors.
(I don't volunteer to do this since I really want to focus on <format>.)