-
Notifications
You must be signed in to change notification settings - Fork 1.6k
Several range algorithms #565
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Conversation
[NB: This includes the changes in microsoft#514 for coherence, we need to merge that PR first.] In `<algorithm>`, implement: * the generic algorithm result types from P2106R0 (lines 75-227) * `ranges::for_each` and its result alias `for_each_result` (lines 289-322) * `ranges::for_each_n` and its result alias `for_each_result_n` (lines 324-351) from P1243R4 * `ranges::find` (lines 353-384) * `ranges::find_if` (lines 396-426) * `ranges::find_if_not` (lines 454-484) * `ranges::count` (lines 526-568) * `ranges::count_if` (lines 587-617) * `ranges::mismatch` and its result alias `mismatch_result` (lines 798-891) * `ranges::equal` (lines 893-980) * `ranges::all_of` (lines 1006-1033) * `ranges::any_of` (lines 1060-1087) * `ranges::none_of` (lines 1114-1141) * `ranges::copy` and its result alias `copy_result` (lines 1143-1175) * `ranges::copy_n` and its result alias `copy_n_result` (lines 1177-1207) * `ranges::copy_if` and its result alias `copy_if_result` (lines 1262-1302) In `<concepts>`: * implement LWG-3194 which includes the resolution of LWG-3151 (lines 51-53) * LWG-3175 has been merged, remove conditional implementation (line 183) * replace `boolean` concept with _`boolean-testable`_ concept from P1964R2 (lines 198-237, 283) * move `movable` (pun intended) into synopsis order (lines 254-256) * Modify concept `copyable` per P2102R0 (lines 260-261) * Implement concept `equivalence_relation` from P1716R3 (lines 290-293) In `<xutility>`: * promote `identity` from `<functional>` for visibility in `<algorithm>` (lines 160-168) * promote `common_range` from `<ranges>` for visibility in `<algorithm>` (lines 3091-3095) * remove LWG-3247 and LWG-3299 annotations (lines 622, 626, and 963) * prefix `indirectly_` to the names of `readable_traits`, `readable`, and `writable` (a great many lines); and modify `iter_value_t` (lines 366-367), `iter_reference_t` (lines ), `iter_difference_t`, `iter_rvalue_reference_t`, `indirectly_readable` (lines 688-701) and `indirectly_swappable` per P1878R1 * define alias template `_Make_unsigned_like_t` to implement P1522R1's _`make-unsigned-like-t`_ (it does nothing interesting yet, since we provide no integer-class types) (lines 727-729) * implement the "Indirect callable" concepts `indirectly_unary_invocable`, `indirectly_regular_unary_invocable`, `indirect_unary_predicate`, `indirect_binary_predicate`, `indirect_equivalence_relation`, `indirect_strict_weak_order`, and helpers `indirect_result_t` and `projected` (lines 852-926) * implement `indirectly_copyable` and `indirectly_copyable_storable` concepts (lines 939-952) * implement `indirectly_swappable`, `indirectly_comparable`, `permutable`, `mergeable`, and `sortable` concepts (lines 1032-1061) * rename `safe_range` and `enable_safe_range` to `borrowed_range` and `enable_borrowed_range` per LWG-3379 (lines 2168-2173 and 2327-2330) * remove "Implements D2091R0" comments (various lines in 2175-2710) * add `ranges::data` to the list of access CPOs that hard error for arrays of incomplete element types (lines 2204-2205 and 2277-2278) * `ranges::empty` rejects arrays of unbound bound per P2091R0 (lines 2664-2692) * implement concept `_Not_same_as` (the exposition-only _`not-same-as`_ from the working draft) (lines 3087-3089) * implement `ranges::dangling` (lines 3097-3102) * implement `ranges::borrowed_iterator_t` (lines 3104-3106) In `<yvals_core.h>`: * Indicate implementation of: * P1207R4 Movability of Single-Pass Iterators * P1248R1 Fixing Relations * P1474R1 Helpful Pointers For contiguous_iterator * P1716R3 Range Comparison Algorithms Are Over-Constrained * P1878R1 Constraining Readable Types * P1964R2 Replacing `boolean` with _`boolean-testable`_ * P2091R0 Fixing Issues With Range Access CPOs * P2102R0 Make "implicit expression variations" More Explicit * and partial implementation of: * P1243R4 Rangify New Algorithms * remove conditional definition of `_HAS_STD_BOOLEAN` (we never has `std::boolean` now) `tests/std/include/instantiate_algorithms.hpp`: * define non-movable type `Immobile`, and use it to ensure that standard algorithms neither copy nor move random number generators nor uniform random bit generators Add header `tests/std/include/range_algorithm_support.hpp` with support machinery for the ranges algorithm tests. It notably defines: * `is_permissive` for determining whether we are compiling in MSVC's permissive mode (lines 18-37) * A class template `borrowed<bool>` whose specializations always model `range` and model `borrowed_range` iff the template parameter is `true` (lines 39-46) * Function objects `get_first` and `get_second` which project the pertinent member from `pair` arguments (lines 48-54) * A class template `move_only_range<T>` which adapts a `contiguous_range` of `T` into a move-only `view` with move-only `input_iterator`s (lines 56-150) * A "phony" iterator class template `test_iterator` with tunable category, value type, and difference capability for instantiation tests (lines 152-363) * A similar "phony" class template `test_range` with tunable category, size, and commonality (i.e., is the sentinel type the same as the iterator type) (lines 365-423) * "phony" predicate and projection types for instantiation tests (lines 425-442) * combinatoric instantiation machinery for instantiation tests that instantiate with all interesting kinds of output iterators or input ranges (lines 444-529) A new compile-only test `tests/std/tests/P0896R4_ranges_algorithm_machinery` which covers: * `indirectly_unary_invocable`/`indirectly_regular_unary_invocable` * `indirect_unary_predicate`/`indirect_binary_predicate`/`indirect_result_t` * `projected` * `indirectly_copyable`/`indirectly_swappable`/`indirectly_comparable` * `dangling`/`borrowed_iterator_t` * the result types `in_found_result`/`in_fun_result`/`in_in_result`/`in_out_result`/`in_in_out_result`/`in_out_out_result`/`min_max_result` Very simple smoke and instantiation tests for the 15 new algorithms in: * `tests/std/tests/P0896R4_ranges_alg_all_of` * `tests/std/tests/P0896R4_ranges_alg_any_of` * `tests/std/tests/P0896R4_ranges_alg_copy` * `tests/std/tests/P0896R4_ranges_alg_copy_if` * `tests/std/tests/P0896R4_ranges_alg_copy_n` * `tests/std/tests/P0896R4_ranges_alg_count` * `tests/std/tests/P0896R4_ranges_alg_count_if` * `tests/std/tests/P0896R4_ranges_alg_equal` * `tests/std/tests/P0896R4_ranges_alg_find` * `tests/std/tests/P0896R4_ranges_alg_find_if` * `tests/std/tests/P0896R4_ranges_alg_find_if_not` * `tests/std/tests/P0896R4_ranges_alg_for_each` * `tests/std/tests/P0896R4_ranges_alg_for_each_n` * `tests/std/tests/P0896R4_ranges_alg_mismatch` * `tests/std/tests/P0896R4_ranges_alg_none_of` Resolves: * microsoft#537 `<concepts>`: LWG-3175 has been accepted, so we should remove commented-out code * microsoft#540 LWG-3194 `ConvertibleTo` prose does not match code * microsoft#546 LWG-3379 `safe` in several library names is misleading * microsoft#559 P1964R2 "Replacing `boolean` with _`boolean-testable`_" * microsoft#561 P2102R0 "Making 'Implicit Expression Variations' More Explicit" * microsoft#563 P2091R0 "Fixing Issues With Range Access CPOs"
miscco
left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Generally I believe that there should be a bigger focus on readability of the concepts. Currently a lot of the more complex concepts are really hard to grog due to unfortunate formatting. I believe that we would gain a lot by spending a few lines more to improve the general readability.
I know that this is a lot of inter twined stuff, but this PR is gargantuan. It would help a lot if small and trivial things like moving identity and renaming safe_range or readable_range would be inside their own PR so that the churn is not that bad.
One can always just base the PR upon the previous ones so one doesnt really loose anything
I agree. I've been trying to format the constraint-expressions in concepts as clang-format would - with the expectation that it will reduce churn someday when clang-format learns to understand concepts and requires-clauses - but I've started cheating here and there when it helps readability. We should simply go all in and format them one-term-per-line (except for very simple cases) as in the Ranges TS. I'll update the concept definitions that this PR touches, and file an issue (#570) to make a general audit.
I apologize to all reviewers: this is a textbook example of a bad PR. I'm trying to cram a large chunk of functionality into a single commit to ease porting to the 16.6 release branch. (This is coming in after the feature freeze via a special exception.) |
|
|
||
| template <input_iterator _It, sentinel_for<_It> _Se, class _Pj = identity, | ||
| indirectly_unary_invocable<projected<_It, _Pj>> _Fn> | ||
| constexpr for_each_result<_It, _Fn> operator()(_It _First, _Se _Last, _Fn _Func, _Pj _Proj = {}) const { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I know this is hot under the wire for .6 but for future algorithms like this I think we need non-_Proj versions so that upgrading to the ranges version doesn't cause serious perf regressions.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
All three of these comments:
- non-projected overloads (or
if constexpred "don't project when the projection isidentity) - reusing bodies with both
stdandrangesalgorithms - engaging low-level optimizations (
memcpy,memcmp)
are interrelated in interesting ways. After thinking through some of the alternatives, I decided they are out of scope for this PR: I don't want to rush out a design, and I especially don't want to break anything in std and delay the release.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Note to self: collect these handwavy promises into the tentative Ranges plan-of-attack and post the result in #39.
| using mismatch_result = in_in_result<_In, _Out>; | ||
|
|
||
| // VARIABLE ranges::mismatch | ||
| class _Mismatch_fn : private _Not_quite_object { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Should we be considering powering the older algorithms with these to avoid repeated definitions?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yes, in the future ;)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Future-Casey is going to love Past-Casey
| _Adl_verify_range(_First, _Last); | ||
| auto _UFirst = _Get_unwrapped(_STD move(_First)); | ||
| const auto _ULast = _Get_unwrapped(_STD move(_Last)); | ||
| for (; _UFirst != _ULast; ++_UFirst, (void) ++_Result) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Lack of attempt to memcpy makes me sad... :(
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yes, future work ;)
BillyONeal
left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I haven't checked that all these things actually do what the Standard says, but given that you wrote most of that .... :)
* Use an asymmetric predicate to test `ranges::equal` * Mirror the structure if `ranges::find_if`'s test in the `ranges::find` test * Remove unused and untested concepts `indirect_equivalence_relation`, `indirect_strict_weak_order`, `indirectly_copyable_storable`, `permutable`, `mergeable`, and `sortable`
StephanTLavavej
left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
One naming typo, otherwise great. Thanks!
Several range algorithms (microsoft#565)
|
Is there a price for "Highest number of issues closed with a single PR"? Great work 🚀 |
Description
[NB: This includes the changes in #514 for coherence, we need to merge that PR first.]
In
<algorithm>, implement:ranges::for_eachand its result aliasfor_each_result(lines 289-322)ranges::for_each_nand its result aliasfor_each_result_n(lines 324-351) from P1243R4ranges::find(lines 353-384)ranges::find_if(lines 396-426)ranges::find_if_not(lines 454-484)ranges::count(lines 526-568)ranges::count_if(lines 587-617)ranges::mismatchand its result aliasmismatch_result(lines 798-891)ranges::equal(lines 893-980)ranges::all_of(lines 1006-1033)ranges::any_of(lines 1060-1087)ranges::none_of(lines 1114-1141)ranges::copyand its result aliascopy_result(lines 1143-1175)ranges::copy_nand its result aliascopy_n_result(lines 1177-1207)ranges::copy_ifand its result aliascopy_if_result(lines 1262-1302)In
<concepts>:booleanconcept withboolean-testableconcept from P1964R2 (lines 198-237, 283)movable(pun intended) into synopsis order (lines 254-256)copyableper P2102R0 (lines 260-261)equivalence_relationfrom P1716R3 (lines 290-293)In
<xutility>:identityfrom<functional>for visibility in<algorithm>(lines 160-168)common_rangefrom<ranges>for visibility in<algorithm>(lines 3091-3095)indirectly_to the names ofreadable_traits,readable, andwritable(a great many lines); and modifyiter_value_t(lines 366-367),iter_reference_t(lines ),iter_difference_t,iter_rvalue_reference_t,indirectly_readable(lines 688-701) andindirectly_swappableper P1878R1_Make_unsigned_like_tto implement P1522R1'smake-unsigned-like-t(it does nothing interesting yet, since we provide no integer-class types) (lines 727-729)indirectly_unary_invocable,indirectly_regular_unary_invocable,indirect_unary_predicate,indirect_binary_predicate, and helpersindirect_result_tandprojected(lines 852-926)indirectly_copyableconcept (lines 939-952)indirectly_swappable,indirectly_comparableconcepts (lines 1032-1061)safe_rangeandenable_safe_rangetoborrowed_rangeandenable_borrowed_rangeper LWG-3379 (lines 2168-2173 and 2327-2330)ranges::datato the list of access CPOs that hard error for arrays of incomplete element types (lines 2204-2205 and 2277-2278)ranges::emptyrejects arrays of unbound bound per P2091R0 (lines 2664-2692)_Not_same_as(the exposition-onlynot-same-asfrom the working draft) (lines 3087-3089)ranges::dangling(lines 3097-3102)ranges::borrowed_iterator_t(lines 3104-3106)In
<yvals_core.h>:booleanwithboolean-testable_HAS_STD_BOOLEAN(we never hasstd::booleannow)tests/std/include/instantiate_algorithms.hpp:Immobile, and use it to ensure that standard algorithms neither copy nor move random number generators nor uniform random bit generatorsAdd header
tests/std/include/range_algorithm_support.hppwith support machinery for the ranges algorithm tests. It notably defines:is_permissivefor determining whether we are compiling in MSVC's permissive mode (lines 18-37)borrowed<bool>whose specializations always modelrangeand modelborrowed_rangeiff the template parameter istrue(lines 39-46)get_firstandget_secondwhich project the pertinent member frompairarguments (lines 48-54)move_only_range<T>which adapts acontiguous_rangeofTinto a move-onlyviewwith move-onlyinput_iterators (lines 56-150)test_iteratorwith tunable category, value type, and difference capability for instantiation tests (lines 152-363)test_rangewith tunable category, size, and commonality (i.e., is the sentinel type the same as the iterator type) (lines 365-423)A new compile-only test
tests/std/tests/P0896R4_ranges_algorithm_machinerywhich covers:indirectly_unary_invocable/indirectly_regular_unary_invocableindirect_unary_predicate/indirect_binary_predicate/indirect_result_tprojectedindirectly_copyable/indirectly_swappable/indirectly_comparabledangling/borrowed_iterator_tin_found_result/in_fun_result/in_in_result/in_out_result/in_in_out_result/in_out_out_result/min_max_resultVery simple smoke and instantiation tests for the 15 new algorithms in:
tests/std/tests/P0896R4_ranges_alg_all_oftests/std/tests/P0896R4_ranges_alg_any_oftests/std/tests/P0896R4_ranges_alg_copytests/std/tests/P0896R4_ranges_alg_copy_iftests/std/tests/P0896R4_ranges_alg_copy_ntests/std/tests/P0896R4_ranges_alg_counttests/std/tests/P0896R4_ranges_alg_count_iftests/std/tests/P0896R4_ranges_alg_equaltests/std/tests/P0896R4_ranges_alg_findtests/std/tests/P0896R4_ranges_alg_find_iftests/std/tests/P0896R4_ranges_alg_find_if_nottests/std/tests/P0896R4_ranges_alg_for_eachtests/std/tests/P0896R4_ranges_alg_for_each_ntests/std/tests/P0896R4_ranges_alg_mismatchtests/std/tests/P0896R4_ranges_alg_none_ofResolves:
<concepts>: LWG-3175 has been accepted, so we should remove commented-out codeConvertibleToprose does not match code #540 LWG-3194ConvertibleToprose does not match codesafein several library names is misleading #546 LWG-3379safein several library names is misleadingbooleanwithboolean-testable"[This is a dual of internal MSVC-PR-232367.]
Checklist
Be sure you've read README.md and understand the scope of this repo.
If you're unsure about a box, leave it unchecked. A maintainer will help you.
_Uglyas perhttps://eel.is/c++draft/lex.name#3.1 or there are no product code changes.
verified by an STL maintainer before automated testing is enabled on GitHub,
leave this unchecked for initial submission).
members, adding virtual functions, changing whether a type is an aggregate
or trivially copyable, etc.).
the C++ Working Draft (including any cited standards), other WG21 papers
(excluding reference implementations outside of proposed standard wording),
and LWG issues as reference material. If they were derived from a project
that's already listed in NOTICE.txt, that's fine, but please mention it.
If they were derived from any other project (including Boost and libc++,
which are not yet listed in NOTICE.txt), you must mention it here,
so we can determine whether the license is compatible and what else needs
to be done.