Skip to content

Implement P2408R5: Ranges Iterators As Inputs To Non-Ranges Algorithms#2960

Merged
StephanTLavavej merged 18 commits intomicrosoft:mainfrom
strega-nil:p2408
Aug 3, 2022
Merged

Implement P2408R5: Ranges Iterators As Inputs To Non-Ranges Algorithms#2960
StephanTLavavej merged 18 commits intomicrosoft:mainfrom
strega-nil:p2408

Conversation

@strega-nil-ms
Copy link
Contributor

@strega-nil-ms strega-nil-ms commented Jul 27, 2022 •
edited
Loading

Fixes #2925

Changes from paper:

  • parallel algorithms: require forward_iterator<FwdIt> when in concepts mode for read-only iterators
  • other algorithms: if there is a static_assert(_Is_blah_iter_v), turn it into a static_assert(_Is_ranges_blah_iter_v), when the iterator is non-mutable
  • sample: check for _Is_ranges_fwd_iter_v
  • unique_copy: check for _Is_ranges_fwd_iter_v

Other changes, not explicitly specified in the paper:

  • many algorithms: if there is a check for different _Is_blah_iter_v, and the iterator in question is non-mutable, check _Is_ranges_blah_iter_v
    • for example, check for _Is_ranges_random_iter_v in advance
  • prev: check for _Is_ranges_bidi_iter_v
  • _Use_atomic_iterators -> check for _Is_ranges_random_iter_v - this has ABI impact

Drive by:

  • fixes _Can_reread_dest to correctly use _Is_fwd_iter_v, not checking for forward_iterator, as it is a mutable iterator
  • add a missed check in rotate_copy(ExPo)

Renamings:

  • _REQUIRE_PARALLEL_ITERATOR becomes two macros:
    • _REQUIRE_PARALLEL_ITERATOR checks for forward_iterator now, and is used for read-only iterators
    • _REQUIRE_CPP17_MUTABLE_ITERATOR checks for _Is_fwd_iter_v (like the old _REQUIRE_PARALLEL_ITERATOR), but has a new message
  • _Is_blah_iter_v -> _Is_cpp17_blah_iter_v - makes it more obvious that we're checking for classic iterators
  • ABI impact from _Use_atomic_iterators
    • _Static_partitioned_find2 -> _Static_partitioned_find3
    • _Static_partitioned_find_end_forward -> _Static_partitioned_find_end_forward2
    • _Static_partitioned_find_end_backward2 -> _Static_partitioned_find_end_backward3
    • _Static_partitioned_adjacent_find2 -> _Static_partitioned_adjacent_find3
    • _Static_partitioned_mismatch2 -> _Static_partitioned_mismatch3
    • _Static_partitioned_search2 -> _Static_partitioned_search3
    • _Static_partitioned_search_n2 -> _Static_partitioned_search_n3
    • _Static_partitioned_is_sorted_until -> _Static_partitioned_is_sorted_until2
    • _Static_partitioned_is_heap_until -> _Static_partitioned_is_heap_until2

@strega-nil-ms strega-nil-ms requested a review from a team as a code owner July 27, 2022 20:46
@strega-nil-ms strega-nil-ms marked this pull request as draft July 27, 2022 21:31
@strega-nil
P2408R5: parallel algorithms
0a3430a 
require `forward_iterator<_It>` instead of `_Is_fwd_iter_v<_It>` for
parallel algorithms
@strega-nil
do the other changes
2103356 
also, add a `_Is_ranges_bidi_iter_v` type trait
@strega-nil-ms strega-nil-ms marked this pull request as ready for review July 27, 2022 23:11
@CaseyCarter CaseyCarter added the cxx23 C++23 feature label Jul 28, 2022
frederick-vs-ja
frederick-vs-ja reviewed Jul 28, 2022
View reviewed changes
Copy link
Contributor

@frederick-vs-ja frederick-vs-ja left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm afraid of reverting improvements introduced by #1794 ...

@strega-nil-ms
Copy link
Contributor Author

strega-nil-ms commented Jul 28, 2022

@frederick-vs-ja For this case, we should only be updating static_asserts and the specific algorithms specified in the paper, and therefore should not have made any changes that break performance.

strega-nil-ms
strega-nil-ms commented Jul 28, 2022
View reviewed changes
StephanTLavavej
StephanTLavavej requested changes Jul 29, 2022
View reviewed changes
miscco
miscco reviewed Jul 29, 2022
View reviewed changes
StephanTLavavej
StephanTLavavej reviewed Aug 2, 2022
View reviewed changes
@StephanTLavavej
Copy link
Member

StephanTLavavej commented Aug 2, 2022

Thanks, this looks good. I've pushed changes for extremely minor test nitpicks, and a tiny bit of missing coverage in the feature-test macro test (also fixing a pre-existing occurrence).

CaseyCarter
CaseyCarter reviewed Aug 2, 2022
View reviewed changes
StephanTLavavej
StephanTLavavej requested changes Aug 2, 2022
View reviewed changes
@CaseyCarter CaseyCarter self-requested a review August 3, 2022 01:30
CaseyCarter
CaseyCarter approved these changes Aug 3, 2022
View reviewed changes
Copy link
Contributor

@CaseyCarter CaseyCarter left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

General comment: I think the wording is strong enough to give us the power to test for sized_sentinel and use it to compute distances for sub-random_access iterators. The potential for breakage is high and the potential benefit smallish, so I'd be happy to see a followup issue to investigate rather than more changes in this PR.

stl/inc/xutility
template <class _Iter>
_INLINE_VAR constexpr bool _Is_random_iter_v = is_convertible_v<_Iter_cat_t<_Iter>, random_access_iterator_tag>;
_INLINE_VAR constexpr bool _Is_ranges_random_iter_v =
#if defined(__cpp_lib_concepts)
Copy link
Contributor

@CaseyCarter CaseyCarter Aug 2, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

#ifdef (not worth resetting testing)

stl/inc/yvals_core.h
#define __cpp_lib_concepts 202002L
#endif // !defined(__EDG__) || defined(__INTELLISENSE__)

#if defined(__cpp_lib_concepts)
Copy link
Contributor

@CaseyCarter CaseyCarter Aug 2, 2022

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ditto #ifdef (not worth resetting testing).

@CaseyCarter
Copy link
Contributor

CaseyCarter commented Aug 3, 2022 •
edited
Loading

I note that the proposal is more hardline than what we're implementing; it says "must model meow_iterator" where we're enforcing more "must model meow_iterator or meet the Cpp17MeowIterator requirements". I think I'm fine with this as-is; the requirements are all preconditions rather than constraints, so we're welcome to define behavior for violations.

EDIT: I forgot to point out that this relaxation of the strict requirements of the proposal is a large part of why I'm comfortable making the change in C++20 mode.

@StephanTLavavej StephanTLavavej mentioned this pull request Aug 3, 2022
Closed
@StephanTLavavej StephanTLavavej self-assigned this Aug 3, 2022
@StephanTLavavej
Copy link
Member

StephanTLavavej commented Aug 3, 2022

I'm mirroring this to the MSVC-internal repo - please notify me if any further changes are pushed.

@StephanTLavavej StephanTLavavej merged commit d9b4534 into microsoft:main Aug 3, 2022
@StephanTLavavej
Copy link
Member

StephanTLavavej commented Aug 3, 2022

Thanks for implementing this C++23 feature/overhaul! 😻 🚀 ✅

strega-nil added a commit to strega-nil/stl that referenced this pull request Aug 6, 2022
@strega-nil-ms @strega-nil @StephanTLavavej
Implement P2408R5: Ranges Iterators As Inputs To Non-Ranges Algorithms (
e490220 
microsoft#2960)

Co-authored-by: Nicole Mazzuca <mazzucan@outlook.com>
Co-authored-by: Stephan T. Lavavej <stl@nuwen.net>
@StephanTLavavej StephanTLavavej mentioned this pull request Aug 8, 2022
Merged
fsb4000 pushed a commit to fsb4000/STL that referenced this pull request Aug 13, 2022
@strega-nil-ms @strega-nil
@StephanTLavavej @fsb4000
Implement P2408R5: Ranges Iterators As Inputs To Non-Ranges Algorithms (
40f5cee 
microsoft#2960)

Co-authored-by: Nicole Mazzuca <mazzucan@outlook.com>
Co-authored-by: Stephan T. Lavavej <stl@nuwen.net>
dkolsen-pgi added a commit to dkolsen-pgi/STL that referenced this pull request Aug 25, 2022
@dkolsen-pgi
Parallel for_each iterators don't have to be mutable
dbdd17f 
The overloads of for_each that take an execution policy argument do not
require that the iterator arguments always be mutable iterators.  Whether
or not the iterators need to be mutable depends on what the function
object does.  for_each is unusual, if not unique, in this regard; for all
other algorithms the mutability of the iterators is specified by the
algorithm.  See http://eel.is/c++draft/alg.foreach#7 , though I admit that
the wording is not particularly clear about this.

Since the compiler can't realiably figure out whether or not the function
object modifies the elements in the sequence, for_each should only check
for constant iterators (_REQUIRE_PARALLEL_ITERATOR), not mutable iterators
(_REQUIRE_CPP17_MUTABLE_ITERATOR).

This bug was introduced by microsoft#2960 .
That PR should not have changed for_each.
@dkolsen-pgi dkolsen-pgi mentioned this pull request Aug 25, 2022
Merged
@strega-nil-ms strega-nil-ms deleted the p2408 branch December 19, 2022 23:42
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@StephanTLavavej StephanTLavavej StephanTLavavej approved these changes

+3 more reviewers

@miscco miscco miscco left review comments

@frederick-vs-ja frederick-vs-ja frederick-vs-ja left review comments

@CaseyCarter CaseyCarter CaseyCarter approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

@StephanTLavavej StephanTLavavej

Labels

cxx23 C++23 feature

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

P2408R5 Ranges Iterators As Inputs To Non-Ranges Algorithms

6 participants

@strega-nil-ms @StephanTLavavej @CaseyCarter @miscco @frederick-vs-ja @strega-nil