Implement range_size_t #514

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.

Sign up for GitHub

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

Jump to bottom

Merged

CaseyCarter merged 5 commits into microsoft:master from miscco:ranges_size_t

Mar 5, 2020

Contributor

miscco commented Feb 19, 2020 •

edited by StephanTLavavej

Loading

Description

This resolves LWG-3335 (at least the applicable parts) by adding ranges_size_t
Note the definition is out of line as the size CPO is defined after the other alias templates

How do we add tests if the features are not yet part of libc++?

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.

Identifiers in product code changes are properly _Ugly as per
https://eel.is/c++draft/lex.name#3.1 or there are no product code changes.
[] The STL builds successfully and all tests have passed (must be manually
verified by an STL maintainer before automated testing is enabled on GitHub,
leave this unchecked for initial submission).
These changes introduce no known ABI breaks (adding members, renaming
members, adding virtual functions, changing whether a type is an aggregate
or trivially copyable, etc.).
These changes were written from scratch using only this repository,
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.


          Implement range_size_t

74b5cdf

this resolves LWG 3335 (at least the applicable parts) by adding ranges_size_t

miscco requested a review from a team as a code owner

February 19, 2020 14:08

Contributor

CaseyCarter commented Feb 19, 2020

How do we add tests if the features are not yet part of libc++?

Add STATIC_ASSERT(std::same_as<ranges::range_size_t<Range>, Size>); hereish.


          Add test

c360fa7

Contributor Author

miscco commented Feb 19, 2020

@CaseyCarter Done, what is the prefered place libc++-tests or those in the repository?

Contributor

CaseyCarter commented Feb 21, 2020

@CaseyCarter Done, what is the prefered place libc++-tests or those in the repository?

If libc++ has a test, turn it on. If it doesn't, or you think the coverage is insufficient, add coverage to tests/std. I've had no luck in the past trying to contribute tests to libc++ for components they don't yet implement. (I suppose there's always the nuclear option: implement the component and the tests in libc++, then implement it here it update the llvm submodule reference to get the newly-added tests.)

CaseyCarter self-assigned this

CaseyCarter approved these changes

View reviewed changes

stl/inc/xutility Outdated Show resolved Hide resolved

CaseyCarter and others added 2 commits

February 21, 2020 12:50


          constrain range_size_t with sized_range instead of range

2b1c509

...per the resolution of LWG-3335.


          Oops - move definition of range_size_t after definition of sized_range

c8607d0

Contributor Author

miscco commented Feb 21, 2020

Should wie add a test for something that is not a sized range to misscompile?


          Test negative cases for range_size_t also

dbe9bb8

Contributor

CaseyCarter commented Feb 21, 2020

Should we add a test for something that is not a sized range to misscompile?

Yes - done.

Contributor Author

miscco commented Feb 21, 2020

@CaseyCarter you are too fast for me, I was still trying to figure out where to put it.

StephanTLavavej added the LWG label

Member

StephanTLavavej commented Feb 26, 2020

Boring issue minutiae: I listed LWG-3335 "range_size_t and views::all_t" in #39 because the latter is unimplemented, instead of filing a separate GitHub issue for it. (This one is strange because it affects code we've already shipped and code that hasn't been implemented yet. The former causes us to file GitHub issues tagged LWG, the latter causes us to mention the necessary work in the GitHub issue tagged cxx20.) I've tagged this PR as LWG as a reminder that it implements half of this issue.

CaseyCarter added a commit to CaseyCarter/STL that referenced this pull request


          Several range algorithms

510488b

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)

Also import microsoftGH-514 "Implement `range_size_t`" which addresses LWG-3335

`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:
* microsoftGH-537 `<concepts>`: LWG-3175 has been accepted, so we should remove commented-out code
* microsoftGH-540 LWG-3194 `ConvertibleTo` prose does not match code
* microsoftGH-546 LWG-3379 `safe` in several library names is misleading
* microsoftGH-559 P1964R2 "Replacing `boolean` with _`boolean-testable`_"
* microsoftGH-561 P2102R0 "Making 'Implicit Expression Variations' More Explicit"
* microsoftGH-563 P2091R0 "Fixing Issues With Range Access CPOs"

CaseyCarter added a commit to CaseyCarter/STL that referenced this pull request


          Several range algorithms

6d2821a

[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"

CaseyCarter mentioned this pull request

Several range algorithms #565

Merged

4 tasks

StephanTLavavej approved these changes

View reviewed changes

Contributor

CaseyCarter commented Mar 5, 2020

Tests/review are finally complete for #565. Thanks for your contribution!

CaseyCarter merged commit 3690083 into microsoft:master

miscco deleted the ranges_size_t branch

March 9, 2020 11:20

CaseyCarter removed their assignment

StephanTLavavej added the ranges label

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels