This is an archive of the discontinued LLVM Phabricator instance.

Differential D123462

[libc++] Implement ranges::fill{, _n}
ClosedPublic

Authored by philnik on Apr 10 2022, 2:27 AM.

Details

Reviewers
ldionne
Mordante
var-const
Group Reviewers
Restricted Project
Commits
rG7af89a379cce: [libc++] Implement ranges::fill{, _n}

Diff Detail

Event Timeline

philnik created this revision.Apr 10 2022, 2:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 10 2022, 2:27 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Apr 10 2022, 2:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 10 2022, 2:27 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Herald added a subscriber: libcxx-commits. · View Herald Transcript
philnik updated this revision to Diff 421777.Apr 10 2022, 2:30 AM
  • Add Synopsis and link
Harbormaster completed remote builds in B158899: Diff 421777.Apr 10 2022, 3:36 AM
var-const requested changes to this revision.Apr 11 2022, 2:18 PM
var-const added inline comments.
libcxx/include/__algorithm/ranges_fill.h
31

Nit: I think contents of a class definition should be indented.

libcxx/include/algorithm
179

Nit: can you move fill_n so that it goes after fill, making it the same order as in the Standard?

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp
15

Please add SFINAE checks for output_iterator and sentinel_for (here and in the other test file).

18

This test doesn't seem to check the case where dangling is returned.

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp
28

Can you also try with a non-trivially-copyable type? (e.g. to make sure that the implementation doesn't just unconditionally use memset)

29

The usual nit about decltype(auto).

50

Hmm, maybe I misunderstand something, but it seems like if elements were copied more than once, this test wouldn't catch that.

60

Question: why is initializing with true necessary?

This revision now requires changes to proceed.Apr 11 2022, 2:18 PM
philnik updated this revision to Diff 422317.Apr 12 2022, 1:02 PM
philnik marked 7 inline comments as done.
  • Address comments
libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp
28

I think we have this discussion in another PR as well. Would it be OK for you if I just add that it's testing non-trivially-copyable things to the description of // check that every element is copied once?

50

Yep. Forgot the assert(!copied).

60

It isn't. I think that was a leftover from a previous iteration of this test.

Harbormaster completed remote builds in B159310: Diff 422317.Apr 12 2022, 2:20 PM
var-const requested changes to this revision.Apr 27 2022, 7:08 PM

Almost LGTM (just one remaining comment). Thanks!

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp
28

I'd prefer to have these test cases separate. For the non-trivially-copyable test, I'd use something that contains a pointer to make sure pointers are deep-copied.

This revision now requires changes to proceed.Apr 27 2022, 7:08 PM
philnik updated this revision to Diff 429540.May 15 2022, 8:52 AM
philnik marked 2 inline comments as done.
  • Rebased
  • Address comments
Harbormaster completed remote builds in B164518: Diff 429540.May 15 2022, 9:32 AM
philnik updated this revision to Diff 431143.May 21 2022, 9:27 AM
  • Try to fix CI
Harbormaster completed remote builds in B165654: Diff 431143.May 21 2022, 11:19 AM
var-const accepted this revision.May 24 2022, 7:03 PM
This revision is now accepted and ready to land.May 24 2022, 7:03 PM
Closed by commit rG7af89a379cce: [libc++] Implement ranges::fill{, _n} (authored by philnik). · Explain WhyMay 25 2022, 1:28 AM
This revision was automatically updated to reflect the committed changes.
philnik added a commit: rG7af89a379cce: [libc++] Implement ranges::fill{, _n}.
ldionne added inline comments.May 25 2022, 6:34 AM
libcxx/include/__algorithm/ranges_fill_n.h
29

Is there any reason for not using std::__fill_n?

Revision Contents

PathSize
libcxx/
docs/
Status/
4 lines
include/
2 lines
__algorithm/
59 lines
48 lines
10 lines
2 lines
test/
libcxx/
2 lines
std/
algorithms/
alg.modifying.operations/
alg.fill/
143 lines
91 lines
support/
38 lines

Diff 431905

libcxx/docs/Status/RangesAlgorithms.csv

Show All 36 Lines
Read-only,for_each,Nikolas Klauser,n/a,✅ Read-only,for_each,Nikolas Klauser,n/a,✅
Read-only,for_each_n,Nikolas Klauser,n/a,✅ Read-only,for_each_n,Nikolas Klauser,n/a,✅
Write,copy,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅ Write,copy,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
Write,copy_if,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅ Write,copy_if,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
Write,copy_n,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅ Write,copy_n,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
Write,copy_backward,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅ Write,copy_backward,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
Write,move,Not assigned,n/a,Not started Write,move,Not assigned,n/a,Not started
Write,move_backward,Not assigned,n/a,Not started Write,move_backward,Not assigned,n/a,Not started
Write,fill,Not assigned,n/a,Not started Write,fill,Nikolas Klauser,`D123462 <https://reviews.llvm.org/D123462>`_,✅
Write,fill_n,Not assigned,n/a,Not started Write,fill_n,Nikolas Klauser,`D123462 <https://reviews.llvm.org/D123462>`_,✅
Write,transform,Nikolas Klauser,`D122173 <https://llvm.org/D122173>`_,✅ Write,transform,Nikolas Klauser,`D122173 <https://llvm.org/D122173>`_,✅
Write,generate,Not assigned,n/a,Not started Write,generate,Not assigned,n/a,Not started
Write,generate_n,Not assigned,n/a,Not started Write,generate_n,Not assigned,n/a,Not started
Write,remove_copy,Not assigned,n/a,Not started Write,remove_copy,Not assigned,n/a,Not started
Write,remove_copy_if,Not assigned,n/a,Not started Write,remove_copy_if,Not assigned,n/a,Not started
Write,replace,Not assigned,n/a,Not started Write,replace,Not assigned,n/a,Not started
Write,replace_if,Not assigned,n/a,Not started Write,replace_if,Not assigned,n/a,Not started
Write,replace_copy,Not assigned,n/a,Not started Write,replace_copy,Not assigned,n/a,Not started
▲ Show 20 Lines • Show All 46 Lines • Show Last 20 Lines

libcxx/include/CMakeLists.txt

Show First 20 Lines • Show All 66 Lines • ▼ Show 20 Linesset(files
__algorithm/prev_permutation.h __algorithm/prev_permutation.h
__algorithm/push_heap.h __algorithm/push_heap.h
__algorithm/ranges_copy.h __algorithm/ranges_copy.h
__algorithm/ranges_copy_backward.h __algorithm/ranges_copy_backward.h
__algorithm/ranges_copy_if.h __algorithm/ranges_copy_if.h
__algorithm/ranges_copy_n.h __algorithm/ranges_copy_n.h
__algorithm/ranges_count.h __algorithm/ranges_count.h
__algorithm/ranges_count_if.h __algorithm/ranges_count_if.h
__algorithm/ranges_fill.h
__algorithm/ranges_fill_n.h
__algorithm/ranges_find.h __algorithm/ranges_find.h
__algorithm/ranges_find_if.h __algorithm/ranges_find_if.h
__algorithm/ranges_find_if_not.h __algorithm/ranges_find_if_not.h
__algorithm/ranges_for_each.h __algorithm/ranges_for_each.h
__algorithm/ranges_for_each_n.h __algorithm/ranges_for_each_n.h
__algorithm/ranges_is_partitioned.h __algorithm/ranges_is_partitioned.h
__algorithm/ranges_max.h __algorithm/ranges_max.h
__algorithm/ranges_max_element.h __algorithm/ranges_max_element.h
▲ Show 20 Lines • Show All 597 Lines • Show Last 20 Lines

libcxx/include/__algorithm/ranges_fill.h

  • This file was added.
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP___ALGORITHM_RANGES_FILL_H
#define _LIBCPP___ALGORITHM_RANGES_FILL_H
#include <__algorithm/ranges_fill_n.h>
#include <__config>
#include <__iterator/concepts.h>
#include <__ranges/access.h>
#include <__ranges/concepts.h>
#include <__ranges/dangling.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
#endif
#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
_LIBCPP_BEGIN_NAMESPACE_STD
namespace ranges {
namespace __fill {
struct __fn {
template <class _Type, output_iterator<const _Type&> _Iter, sentinel_for<_Iter> _Sent>
_LIBCPP_HIDE_FROM_ABI constexpr
var-constUnsubmitted
Done
ReplyInline Actions

Nit: I think contents of a class definition should be indented.

var-const: Nit: I think contents of a class definition should be indented.
_Iter operator()(_Iter __first, _Sent __last, const _Type& __value) const {
if constexpr(random_access_iterator<_Iter>) {
return ranges::fill_n(__first, __last - __first, __value);
} else {
for (; __first != __last; ++__first)
*__first = __value;
return __first;
}
}
template <class _Type, output_range<const _Type&> _Range>
_LIBCPP_HIDE_FROM_ABI constexpr
borrowed_iterator_t<_Range> operator()(_Range&& __range, const _Type& __value) const {
return (*this)(ranges::begin(__range), ranges::end(__range), __value);
}
};
} // namespace __fill
inline namespace __cpo {
inline constexpr auto fill = __fill::__fn{};
} // namespace __cpo
} // namespace ranges
_LIBCPP_END_NAMESPACE_STD
#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
#endif // _LIBCPP___ALGORITHM_RANGES_FILL_H

libcxx/include/__algorithm/ranges_fill_n.h

  • This file was added.
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP___ALGORITHM_RANGES_FILL_N_H
#define _LIBCPP___ALGORITHM_RANGES_FILL_N_H
#include <__config>
#include <__iterator/concepts.h>
#include <__iterator/incrementable_traits.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
#endif
#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
_LIBCPP_BEGIN_NAMESPACE_STD
namespace ranges {
namespace __fill_n {
struct __fn {
template <class _Type, output_iterator<const _Type&> _Iter>
_LIBCPP_HIDE_FROM_ABI constexpr
_Iter operator()(_Iter __first, iter_difference_t<_Iter> __n, const _Type& __value) const {
ldionneUnsubmitted
Not Done
ReplyInline Actions

Is there any reason for not using std::__fill_n?

ldionne: Is there any reason for not using `std::__fill_n`?
for (; __n != 0; --__n) {
*__first = __value;
++__first;
}
return __first;
}
};
} // namespace __fill_n
inline namespace __cpo {
inline constexpr auto fill_n = __fill_n::__fn{};
} // namespace __cpo
} // namespace ranges
_LIBCPP_END_NAMESPACE_STD
#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
#endif // _LIBCPP___ALGORITHM_RANGES_FILL_N_H

libcxx/include/algorithm

Show First 20 Lines • Show All 170 Lines • ▼ Show 20 Lines constexpr iter_difference_t<I>
count_if(I first, S last, Pred pred, Proj proj = {}); // since C++20 count_if(I first, S last, Pred pred, Proj proj = {}); // since C++20
template<input_range R, class Proj = identity, template<input_range R, class Proj = identity,
indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr range_difference_t<R> constexpr range_difference_t<R>
count_if(R&& r, Pred pred, Proj proj = {}); // since C++20 count_if(R&& r, Pred pred, Proj proj = {}); // since C++20
template<class T, class Proj = identity, template<class T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less> indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
var-constUnsubmitted
Done
ReplyInline Actions

Nit: can you move fill_n so that it goes after fill, making it the same order as in the Standard?

var-const: Nit: can you move `fill_n` so that it goes after `fill`, making it the same order as in the…
constexpr ranges::minmax_result<const T&> constexpr ranges::minmax_result<const T&>
minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20 minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {}); // since C++20
template<copyable T, class Proj = identity, template<copyable T, class Proj = identity,
indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less> indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
constexpr ranges::minmax_result<T> constexpr ranges::minmax_result<T>
minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20 minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {}); // since C++20
▲ Show 20 Lines • Show All 90 Lines • ▼ Show 20 Lines template<input_range R, class Proj = identity,
template<bidirectional_iterator I, sentinel_for<I> S> template<bidirectional_iterator I, sentinel_for<I> S>
requires permutable<I> requires permutable<I>
constexpr I ranges::reverse(I first, S last); // since C++20 constexpr I ranges::reverse(I first, S last); // since C++20
template<bidirectional_range R> template<bidirectional_range R>
requires permutable<iterator_t<R>> requires permutable<iterator_t<R>>
constexpr borrowed_iterator_t<R> ranges::reverse(R&& r); // since C++20 constexpr borrowed_iterator_t<R> ranges::reverse(R&& r); // since C++20
template<class T, output_iterator<const T&> O, sentinel_for<O> S>
constexpr O ranges::fill(O first, S last, const T& value); // since C++20
template<class T, output_range<const T&> R>
constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value); // since C++20
template<class T, output_iterator<const T&> O>
constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value); // since C++20
} }
constexpr bool // constexpr in C++20 constexpr bool // constexpr in C++20
all_of(InputIterator first, InputIterator last, Predicate pred); all_of(InputIterator first, InputIterator last, Predicate pred);
template <class InputIterator, class Predicate> template <class InputIterator, class Predicate>
constexpr bool // constexpr in C++20 constexpr bool // constexpr in C++20
any_of(InputIterator first, InputIterator last, Predicate pred); any_of(InputIterator first, InputIterator last, Predicate pred);
▲ Show 20 Lines • Show All 706 Lines • ▼ Show 20 Lines
#include <__algorithm/prev_permutation.h> #include <__algorithm/prev_permutation.h>
#include <__algorithm/push_heap.h> #include <__algorithm/push_heap.h>
#include <__algorithm/ranges_copy.h> #include <__algorithm/ranges_copy.h>
#include <__algorithm/ranges_copy_backward.h> #include <__algorithm/ranges_copy_backward.h>
#include <__algorithm/ranges_copy_if.h> #include <__algorithm/ranges_copy_if.h>
#include <__algorithm/ranges_copy_n.h> #include <__algorithm/ranges_copy_n.h>
#include <__algorithm/ranges_count.h> #include <__algorithm/ranges_count.h>
#include <__algorithm/ranges_count_if.h> #include <__algorithm/ranges_count_if.h>
#include <__algorithm/ranges_fill.h>
#include <__algorithm/ranges_fill_n.h>
#include <__algorithm/ranges_find.h> #include <__algorithm/ranges_find.h>
#include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if.h>
#include <__algorithm/ranges_find_if_not.h> #include <__algorithm/ranges_find_if_not.h>
#include <__algorithm/ranges_for_each.h> #include <__algorithm/ranges_for_each.h>
#include <__algorithm/ranges_for_each_n.h> #include <__algorithm/ranges_for_each_n.h>
#include <__algorithm/ranges_is_partitioned.h> #include <__algorithm/ranges_is_partitioned.h>
#include <__algorithm/ranges_max.h> #include <__algorithm/ranges_max.h>
#include <__algorithm/ranges_max_element.h> #include <__algorithm/ranges_max_element.h>
▲ Show 20 Lines • Show All 51 Lines • Show Last 20 Lines

libcxx/include/module.modulemap

Show First 20 Lines • Show All 298 Lines • ▼ Show 20 Lines module __algorithm {
module prev_permutation { private header "__algorithm/prev_permutation.h" } module prev_permutation { private header "__algorithm/prev_permutation.h" }
module push_heap { private header "__algorithm/push_heap.h" } module push_heap { private header "__algorithm/push_heap.h" }
module ranges_copy { private header "__algorithm/ranges_copy.h" } module ranges_copy { private header "__algorithm/ranges_copy.h" }
module ranges_copy_backward { private header "__algorithm/ranges_copy_backward.h" } module ranges_copy_backward { private header "__algorithm/ranges_copy_backward.h" }
module ranges_copy_if { private header "__algorithm/ranges_copy_if.h" } module ranges_copy_if { private header "__algorithm/ranges_copy_if.h" }
module ranges_copy_n { private header "__algorithm/ranges_copy_n.h" } module ranges_copy_n { private header "__algorithm/ranges_copy_n.h" }
module ranges_count { private header "__algorithm/ranges_count.h" } module ranges_count { private header "__algorithm/ranges_count.h" }
module ranges_count_if { private header "__algorithm/ranges_count_if.h" } module ranges_count_if { private header "__algorithm/ranges_count_if.h" }
module ranges_fill { private header "__algorithm/ranges_fill.h" }
module ranges_fill_n { private header "__algorithm/ranges_fill_n.h" }
module ranges_find { private header "__algorithm/ranges_find.h" } module ranges_find { private header "__algorithm/ranges_find.h" }
module ranges_find_if { private header "__algorithm/ranges_find_if.h" } module ranges_find_if { private header "__algorithm/ranges_find_if.h" }
module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.h" } module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.h" }
module ranges_for_each { private header "__algorithm/ranges_for_each.h" } module ranges_for_each { private header "__algorithm/ranges_for_each.h" }
module ranges_for_each_n { private header "__algorithm/ranges_for_each_n.h" } module ranges_for_each_n { private header "__algorithm/ranges_for_each_n.h" }
module ranges_is_partitioned { private header "__algorithm/ranges_is_partitioned.h" } module ranges_is_partitioned { private header "__algorithm/ranges_is_partitioned.h" }
module ranges_max { private header "__algorithm/ranges_max.h" } module ranges_max { private header "__algorithm/ranges_max.h" }
module ranges_max_element { private header "__algorithm/ranges_max_element.h" } module ranges_max_element { private header "__algorithm/ranges_max_element.h" }
▲ Show 20 Lines • Show All 873 Lines • Show Last 20 Lines

libcxx/test/libcxx/private_headers.verify.cpp

Show First 20 Lines • Show All 103 Lines • ▼ Show 20 Lines
#include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}} #include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}}
#include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}} #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}}
#include <__algorithm/ranges_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy.h'}} #include <__algorithm/ranges_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy.h'}}
#include <__algorithm/ranges_copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_backward.h'}} #include <__algorithm/ranges_copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_backward.h'}}
#include <__algorithm/ranges_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_if.h'}} #include <__algorithm/ranges_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_if.h'}}
#include <__algorithm/ranges_copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_n.h'}} #include <__algorithm/ranges_copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_n.h'}}
#include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}} #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}}
#include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}} #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}}
#include <__algorithm/ranges_fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill.h'}}
#include <__algorithm/ranges_fill_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill_n.h'}}
#include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}} #include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}}
#include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}} #include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}}
#include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}} #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}}
#include <__algorithm/ranges_for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each.h'}} #include <__algorithm/ranges_for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each.h'}}
#include <__algorithm/ranges_for_each_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each_n.h'}} #include <__algorithm/ranges_for_each_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each_n.h'}}
#include <__algorithm/ranges_is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_partitioned.h'}} #include <__algorithm/ranges_is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_partitioned.h'}}
#include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}} #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
#include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}} #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
▲ Show 20 Lines • Show All 371 Lines • Show Last 20 Lines

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp

  • This file was added.
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// <algorithm>
// UNSUPPORTED: c++03, c++11, c++14, c++17
// UNSUPPORTED: libcpp-has-no-incomplete-ranges
// template<class T, output_iterator<const T&> O, sentinel_for<O> S>
// constexpr O ranges::fill(O first, S last, const T& value);
var-constUnsubmitted
Done
ReplyInline Actions

Please add SFINAE checks for output_iterator and sentinel_for (here and in the other test file).

var-const: Please add SFINAE checks for `output_iterator` and `sentinel_for` (here and in the other test…
// template<class T, output_range<const T&> R>
// constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);
var-constUnsubmitted
Done
ReplyInline Actions

This test doesn't seem to check the case where dangling is returned.

var-const: This test doesn't seem to check the case where `dangling` is returned.
#include <algorithm>
#include <array>
#include <cassert>
#include <ranges>
#include <string>
#include "almost_satisfies_types.h"
#include "test_iterators.h"
template <class Iter, class Sent = sentinel_wrapper<Iter>>
concept HasFillIt = requires(Iter iter, Sent sent) { std::ranges::fill(iter, sent, int{}); };
static_assert(HasFillIt<int*>);
static_assert(!HasFillIt<OutputIteratorNotIndirectlyWritable>);
static_assert(!HasFillIt<OutputIteratorNotInputOrOutputIterator>);
static_assert(!HasFillIt<int*, SentinelForNotSemiregular>);
static_assert(!HasFillIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
template <class Range>
concept HasFillR = requires(Range range) { std::ranges::fill(range, int{}); };
static_assert(HasFillR<UncheckedRange<int*>>);
static_assert(!HasFillR<OutputRangeNotIndirectlyWritable>);
static_assert(!HasFillR<OutputRangeNotInputOrOutputIterator>);
static_assert(!HasFillR<OutputRangeNotSentinelSemiregular>);
static_assert(!HasFillR<OutputRangeNotSentinelEqualityComparableWith>);
template <class It, class Sent = It>
constexpr void test_iterators() {
{ // simple test
{
int a[3];
std::same_as<It> auto ret = std::ranges::fill(It(a), Sent(It(a + 3)), 1);
assert(std::all_of(a, a + 3, [](int i) { return i == 1; }));
assert(base(ret) == a + 3);
}
{
int a[3];
auto range = std::ranges::subrange(It(a), Sent(It(a + 3)));
std::same_as<It> auto ret = std::ranges::fill(range, 1);
assert(std::all_of(a, a + 3, [](int i) { return i == 1; }));
assert(base(ret) == a + 3);
}
}
{ // check that an empty range works
{
std::array<int, 0> a;
auto ret = std::ranges::fill(It(a.data()), Sent(It(a.data())), 1);
assert(base(ret) == a.data());
}
{
std::array<int, 0> a;
auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data())));
auto ret = std::ranges::fill(range, 1);
assert(base(ret) == a.data());
}
}
}
constexpr bool test() {
test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>();
test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>();
test_iterators<forward_iterator<int*>>();
test_iterators<bidirectional_iterator<int*>>();
test_iterators<random_access_iterator<int*>>();
test_iterators<contiguous_iterator<int*>>();
test_iterators<int*>();
{ // check that every element is copied once
struct S {
bool copied = false;
constexpr S& operator=(const S&) {
copied = true;
return *this;
}
};
{
S a[5];
std::ranges::fill(a, a + 5, S {true});
assert(std::all_of(a, a + 5, [](S& s) { return s.copied; }));
}
{
S a[5];
std::ranges::fill(a, S {true});
assert(std::all_of(a, a + 5, [](S& s) { return s.copied; }));
}
}
{ // check that std::ranges::dangling is returned
[[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
std::ranges::fill(std::array<int, 10> {}, 1);
}
{ // check that std::ranges::dangling isn't returned with a borrowing range
std::array<int, 10> a{};
[[maybe_unused]] std::same_as<std::array<int, 10>::iterator> decltype(auto) ret =
std::ranges::fill(std::views::all(a), 1);
assert(std::all_of(a.begin(), a.end(), [](int i) { return i == 1; }));
}
{ // check that non-trivially copyable items are copied properly
{
std::array<std::string, 10> a;
auto ret = std::ranges::fill(a.begin(), a.end(), "long long string so no SSO");
assert(ret == a.data() + a.size());
assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; }));
}
{
std::array<std::string, 10> a;
auto ret = std::ranges::fill(a, "long long string so no SSO");
assert(ret == a.data() + a.size());
assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; }));
}
}
return true;
}
int main(int, char**) {
test();
static_assert(test());
return 0;
}

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp

  • This file was added.
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// <algorithm>
// UNSUPPORTED: c++03, c++11, c++14, c++17
// UNSUPPORTED: libcpp-has-no-incomplete-ranges
// template<class T, output_iterator<const T&> O>
// constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);
#include <algorithm>
#include <array>
#include <cassert>
#include <ranges>
#include <string>
#include "almost_satisfies_types.h"
#include "test_iterators.h"
template <class Iter>
concept HasFillN = requires(Iter iter) { std::ranges::fill_n(iter, int{}, int{}); };
var-constUnsubmitted
Done
ReplyInline Actions

Can you also try with a non-trivially-copyable type? (e.g. to make sure that the implementation doesn't just unconditionally use memset)

var-const: Can you also try with a non-trivially-copyable type? (e.g. to make sure that the implementation…
philnikAuthorUnsubmitted
Done
ReplyInline Actions

I think we have this discussion in another PR as well. Would it be OK for you if I just add that it's testing non-trivially-copyable things to the description of // check that every element is copied once?

philnik: I think we have this discussion in another PR as well. Would it be OK for you if I just add…
var-constUnsubmitted
Done
ReplyInline Actions

I'd prefer to have these test cases separate. For the non-trivially-copyable test, I'd use something that contains a pointer to make sure pointers are deep-copied.

var-const: I'd prefer to have these test cases separate. For the non-trivially-copyable test, I'd use…
struct WrongType {};
var-constUnsubmitted
Done
ReplyInline Actions

The usual nit about decltype(auto).

var-const: The usual nit about `decltype(auto)`.
static_assert(HasFillN<int*>);
static_assert(!HasFillN<WrongType*>);
static_assert(!HasFillN<OutputIteratorNotIndirectlyWritable>);
static_assert(!HasFillN<OutputIteratorNotInputOrOutputIterator>);
template <class It, class Sent = It>
constexpr void test_iterators() {
{ // simple test
int a[3];
std::same_as<It> decltype(auto) ret = std::ranges::fill_n(It(a), 3, 1);
assert(std::all_of(a, a + 3, [](int i) { return i == 1; }));
assert(base(ret) == a + 3);
}
{ // check that an empty range works
std::array<int, 0> a;
auto ret = std::ranges::fill_n(It(a.data()), 0, 1);
assert(base(ret) == a.data());
}
}
var-constUnsubmitted
Done
ReplyInline Actions

Hmm, maybe I misunderstand something, but it seems like if elements were copied more than once, this test wouldn't catch that.

var-const: Hmm, maybe I misunderstand something, but it seems like if elements were copied more than once…
philnikAuthorUnsubmitted
Done
ReplyInline Actions

Yep. Forgot the assert(!copied).

philnik: Yep. Forgot the `assert(!copied)`.
constexpr bool test() {
test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>();
test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>();
test_iterators<forward_iterator<int*>>();
test_iterators<bidirectional_iterator<int*>>();
test_iterators<random_access_iterator<int*>>();
test_iterators<contiguous_iterator<int*>>();
test_iterators<int*>();
var-constUnsubmitted
Done
ReplyInline Actions

Question: why is initializing with true necessary?

var-const: Question: why is initializing with `true` necessary?
philnikAuthorUnsubmitted
Done
ReplyInline Actions

It isn't. I think that was a leftover from a previous iteration of this test.

philnik: It isn't. I think that was a leftover from a previous iteration of this test.
{ // check that every element is copied once
struct S {
bool copied = false;
constexpr S& operator=(const S&) {
assert(!copied);
copied = true;
return *this;
}
};
S a[5];
std::ranges::fill_n(a, 5, S {});
assert(std::all_of(a, a + 5, [](S& s) { return s.copied; }));
}
{ // check that non-trivially copyable items are copied properly
std::array<std::string, 10> a;
auto ret = std::ranges::fill_n(a.data(), 10, "long long string so no SSO");
assert(ret == a.data() + a.size());
assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; }));
}
return true;
}
int main(int, char**) {
test();
static_assert(test());
return 0;
}

libcxx/test/support/almost_satisfies_types.h

Show First 20 Lines • Show All 101 Lines • ▼ Show 20 Linespublic:
using difference_type = long; using difference_type = long;
SentinelForNotSemiregular& operator++(); SentinelForNotSemiregular& operator++();
void operator++(int); void operator++(int);
const int& operator*() const; const int& operator*() const;
friend bool operator==(const SentinelForNotSemiregular&, const cpp20_input_iterator<int*>&); friend bool operator==(const SentinelForNotSemiregular&, const cpp20_input_iterator<int*>&);
}; };
using InputRangeNotSentinelSemiregular = UncheckedRange<cpp20_input_iterator<int*>, SentinelForNotSemiregular>; using InputRangeNotSentinelSemiregular = UncheckedRange<cpp20_input_iterator<int*>, SentinelForNotSemiregular>;
using OutputRangeNotSentinelSemiregular = UncheckedRange<cpp20_output_iterator<int*>, SentinelForNotSemiregular>;
static_assert(std::input_or_output_iterator<SentinelForNotSemiregular>); static_assert(std::input_or_output_iterator<SentinelForNotSemiregular>);
static_assert(!std::semiregular<SentinelForNotSemiregular>); static_assert(!std::semiregular<SentinelForNotSemiregular>);
static_assert(!std::sentinel_for<SentinelForNotSemiregular, cpp20_input_iterator<int*>>); static_assert(!std::sentinel_for<SentinelForNotSemiregular, cpp20_input_iterator<int*>>);
// almost a sentinel_for cpp20_input_iterator // almost a sentinel_for cpp20_input_iterator
class SentinelForNotWeaklyEqualityComparableWith { class SentinelForNotWeaklyEqualityComparableWith {
public: public:
using difference_type = long; using difference_type = long;
SentinelForNotWeaklyEqualityComparableWith& operator++(); SentinelForNotWeaklyEqualityComparableWith& operator++();
void operator++(int); void operator++(int);
const int& operator*() const; const int& operator*() const;
}; };
using InputRangeNotSentinelEqualityComparableWith = using InputRangeNotSentinelEqualityComparableWith =
UncheckedRange<cpp20_input_iterator<int*>, SentinelForNotWeaklyEqualityComparableWith>; UncheckedRange<cpp20_input_iterator<int*>, SentinelForNotWeaklyEqualityComparableWith>;
using OutputRangeNotSentinelEqualityComparableWith =
UncheckedRange<cpp20_output_iterator<int*>, SentinelForNotWeaklyEqualityComparableWith>;
static_assert(std::input_or_output_iterator<SentinelForNotWeaklyEqualityComparableWith>); static_assert(std::input_or_output_iterator<SentinelForNotWeaklyEqualityComparableWith>);
static_assert(std::semiregular<SentinelForNotWeaklyEqualityComparableWith>); static_assert(std::semiregular<SentinelForNotWeaklyEqualityComparableWith>);
static_assert(!std::sentinel_for<SentinelForNotWeaklyEqualityComparableWith, cpp20_input_iterator<int*>>); static_assert(!std::sentinel_for<SentinelForNotWeaklyEqualityComparableWith, cpp20_input_iterator<int*>>);
class WeaklyIncrementableNotMovable { class WeaklyIncrementableNotMovable {
public: public:
using difference_type = long; using difference_type = long;
▲ Show 20 Lines • Show All 81 Lines • ▼ Show 20 Lines
using PermutableRangeNotSwappable = UncheckedRange<PermutableNotSwappable>; using PermutableRangeNotSwappable = UncheckedRange<PermutableNotSwappable>;
static_assert(std::input_iterator<PermutableNotSwappable>); static_assert(std::input_iterator<PermutableNotSwappable>);
static_assert(std::forward_iterator<PermutableNotSwappable>); static_assert(std::forward_iterator<PermutableNotSwappable>);
static_assert(!std::permutable<PermutableNotSwappable>); static_assert(!std::permutable<PermutableNotSwappable>);
static_assert(!std::indirectly_swappable<PermutableNotSwappable>); static_assert(!std::indirectly_swappable<PermutableNotSwappable>);
class OutputIteratorNotInputOrOutputIterator {
public:
using difference_type = long;
using value_type = int;
using iterator_category = std::input_iterator_tag;
int& operator++();
void operator++(int);
int& operator*();
};
using OutputRangeNotInputOrOutputIterator = UncheckedRange<InputIteratorNotInputOrOutputIterator>;
static_assert(!std::input_or_output_iterator<OutputIteratorNotInputOrOutputIterator>);
static_assert(std::indirectly_writable<OutputIteratorNotInputOrOutputIterator, int>);
static_assert(!std::output_iterator<OutputIteratorNotInputOrOutputIterator, int>);
static_assert(!std::ranges::input_range<OutputRangeNotInputOrOutputIterator>);
class OutputIteratorNotIndirectlyWritable {
public:
using difference_type = long;
using iterator_category = std::input_iterator_tag;
OutputIteratorNotIndirectlyWritable& operator++();
void operator++(int);
const int& operator*() const;
};
using OutputRangeNotIndirectlyWritable = UncheckedRange<OutputIteratorNotIndirectlyWritable>;
static_assert(std::input_or_output_iterator<OutputIteratorNotIndirectlyWritable>);
static_assert(!std::indirectly_writable<OutputIteratorNotIndirectlyWritable, int>);
static_assert(!std::output_iterator<OutputIteratorNotIndirectlyWritable, int>);
static_assert(!std::ranges::output_range<OutputIteratorNotIndirectlyWritable, int>);
#endif // ALMOST_SATISFIES_TYPES_H #endif // ALMOST_SATISFIES_TYPES_H