This is an archive of the discontinued LLVM Phabricator instance.

Differential D122074

[libc++] Allow an output_iterator in fill.
AbandonedPublic

Authored by Mordante on Mar 19 2022, 10:56 AM.

Details

Reviewers
ldionne
Group Reviewers
Restricted Project
Summary

This isn't required by the Standard but is an QoI extension.

This extension isn't only benificial for users but avoids code
duplication libc++. The ouput iterator in std::format only needs to
satisfy the output_iterator concept and not the Cpp17OutputIterator
requirements. This means a conforming std::format implementation can't
use the available algorithms and needs to write their own.

Note: This is the first patch, there will be follow-up patches making
this change to other algorithms.

Depends on D122072

Diff Detail

Event Timeline

Mordante created this revision.Mar 19 2022, 10:56 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 19 2022, 10:56 AM
Mordante requested review of this revision.Mar 19 2022, 10:56 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 19 2022, 10:56 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Herald added a subscriber: libcxx-commits. · View Herald Transcript
philnik added a subscriber: philnik.Mar 19 2022, 11:01 AM

Would ranges::fill_n work for your purposes? If yes, maybe just use that (I can work on implementing it) instead of adding an extension?

Harbormaster completed remote builds in B155209: Diff 416710.Mar 19 2022, 11:10 AM
Mordante updated this revision to Diff 416712.Mar 19 2022, 11:14 AM

Fix CI.

Mordante added a comment.Mar 19 2022, 11:52 AM
In D122074#3394314, @philnik wrote:

Would ranges::fill_n work for your purposes? If yes, maybe just use that (I can work on implementing it) instead of adding an extension?

Good point, when I initially ran into this issue ranges was quite less mature so I never even considered it. But it should be possible.
If you want to look into it that would be great! From a quick look at the format code I use copy, copy_n, fill_n, and transform.

The copy and copy_n are a bit tricky due to the wrap_iterator.

@ldionne Do you see any value in this extension or do you prefer to abandon this patch?

Mordante mentioned this in D122072: [libc++][test] Adds an cpp20_output_iterator..Mar 19 2022, 11:55 AM
Harbormaster completed remote builds in B155211: Diff 416712.Mar 19 2022, 12:25 PM
ldionne added a comment.Mar 23 2022, 12:58 PM

Interesting patch! On the one hand I don't really want to commit to this extension (extensions are evil!), however it does seem to me like moving instead of copying the iterator is an improvement, and it's trivial to do. It's also clearly conforming.

This leads me to wonder whether the standard could relax those restrictions itself. Would you have any interest in investigating that with a short paper?

I would suggest one of two things for the time being:

  1. Either you add std::move to std::fill and start using it in <format>, but you put the rest of this patch on the ice until we have clarity about relaxing this in the Standard (i.e. you don't add tests or documentation that would commit us to an extension), or
  2. You use ranges::fill instead in <format> and you put this patch on the ice until we have clarity, or you abandon it.

In other words, if you want to keep using std::fill instead of ranges::fill in <format>, I would be fine with relaxing the requirement as an implementation detail in std::fill, but not to commit to the extension until we have clarity about doing it in the Standard per se. I hope this makes sense?

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp
151
162
Mordante planned changes to this revision.Mar 23 2022, 1:24 PM

Thanks for the feedback!
In that case I put this patch on hold. In format I'm not only using fill, but several other algorithms like copy and transform. So only doing one algorithm makes little sense. I only did this one patch to float the idea. Especially copy is a more effort due to the wrap iterator.

As mentioned on Discord when I started to work on this patch these algorithms in ranges were still far off, now they are not that far off. When I restarted working on it recently I didn't really think about the ranges versions anymore until @philnik asked an excellent question.

I like your suggestion about writing a paper. I was surprised these iterators in <algorithm> didn't change in C++20. But I can't recall seeing a paper suggesting this direction. I'll have a look whether there has been a paper, if not I will consider writing one.

philnik mentioned this in D122982: [libc++] Implement ranges::copy{, _n, _if, _backward}.Apr 5 2022, 1:53 AM
Mordante abandoned this revision.Sep 28 2022, 12:14 PM

With ranges completed there's no need to use pre-C++20 algorithms. Since it will be quite a bit of effort to adjust all algorithms and it has a very low priority I abandon this instead.

Revision Contents

PathSize
libcxx/
docs/
16 lines
include/
__algorithm/
3 lines
test/
std/
algorithms/
alg.modifying.operations/
alg.fill/
10 lines

Diff 416712

libcxx/docs/UsingLibcxx.rst

Show First 20 Lines • Show All 339 Lines • ▼ Show 20 Lines
* ``as_const`` * ``as_const``
* ``bit_cast`` * ``bit_cast``
* ``forward`` * ``forward``
* ``move`` * ``move``
* ``move_if_noexcept`` * ``move_if_noexcept``
* ``identity::operator()`` * ``identity::operator()``
* ``to_integer`` * ``to_integer``
* ``to_underlying`` * ``to_underlying``
Lowered requirements of ``OutputIterator`` in ``<algorithm>``
-------------------------------------------------------------
In C++20 the Standard changed the iterator requirements, but the requirements
for the iterators in ``<algorithm>`` remained unchanged. As an extension
several algorithms in ``<algorithm>`` now only require the ``OutputIterator``
to satisfy the ``output_iterator`` concept instead of the
``Cpp17OutputIterator`` requirement. From a user's perspective the main change
is that a movable non-copyable ``OutputIterator`` is now allowed in all
language versions.
Theses changes have been applied to the following algorithms:
* ``fill_n``

libcxx/include/__algorithm/fill_n.h

//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
Lint: Lint
Inline Actions

clang-format suggested style edits found:

Lint: Lint: clang-format suggested style edits found:
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef _LIBCPP___ALGORITHM_FILL_N_H #ifndef _LIBCPP___ALGORITHM_FILL_N_H
#define _LIBCPP___ALGORITHM_FILL_N_H #define _LIBCPP___ALGORITHM_FILL_N_H
#include <__config> #include <__config>
#include <__iterator/iterator_traits.h> #include <__iterator/iterator_traits.h>
#include <__utility/move.h>
#include <type_traits> #include <type_traits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header # pragma GCC system_header
#endif #endif
_LIBCPP_BEGIN_NAMESPACE_STD _LIBCPP_BEGIN_NAMESPACE_STD
template <class _OutputIterator, class _Size, class _Tp> template <class _OutputIterator, class _Size, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
_OutputIterator _OutputIterator
__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
{ {
for (; __n > 0; ++__first, (void) --__n) for (; __n > 0; ++__first, (void) --__n)
*__first = __value_; *__first = __value_;
return __first; return __first;
} }
template <class _OutputIterator, class _Size, class _Tp> template <class _OutputIterator, class _Size, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
_OutputIterator _OutputIterator
fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
{ {
return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value_); return std::__fill_n(std::move(__first), std::__convert_to_integral(__n), __value_);
} }
_LIBCPP_END_NAMESPACE_STD _LIBCPP_END_NAMESPACE_STD
#endif // _LIBCPP___ALGORITHM_FILL_N_H #endif // _LIBCPP___ALGORITHM_FILL_N_H

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

//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
Lint: Lint
Inline Actions

clang-format suggested style edits found:

Lint: Lint: clang-format suggested style edits found:
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// <algorithm> // <algorithm>
▲ Show 20 Lines • Show All 133 Lines • ▼ Show 20 Linesvoid test6()
Storage foo[5]; Storage foo[5];
std::fill_n(&foo[0], UDI(5), Storage()); std::fill_n(&foo[0], UDI(5), Storage());
} }
int main(int, char**) int main(int, char**)
{ {
test_char<cpp17_output_iterator<char*> >(); test_char<cpp17_output_iterator<char*> >();
#if _LIBCPP_VERSION
ldionneUnsubmitted
Not Done
ReplyInline Actions
test_char<cpp17_output_iterator<char*> >();
- #if _LIBCPP_VERSION
+ #ifdef _LIBCPP_VERSION
// The iterator statisfies the output_iterator concept but not the
ldionne:
// The iterator statisfies the output_iterator concept but not the
// Cpp17OutputIterator allowing this in <algorithm> is a libc++ extension.
test_char<cpp20_output_iterator<char*> >();
#endif
test_char<forward_iterator<char*> >(); test_char<forward_iterator<char*> >();
test_char<bidirectional_iterator<char*> >(); test_char<bidirectional_iterator<char*> >();
test_char<random_access_iterator<char*> >(); test_char<random_access_iterator<char*> >();
test_char<char*>(); test_char<char*>();
test_int<cpp17_output_iterator<int*> >(); test_int<cpp17_output_iterator<int*> >();
#if _LIBCPP_VERSION
ldionneUnsubmitted
Not Done
ReplyInline Actions
test_int<cpp17_output_iterator<int*> >();
- #if _LIBCPP_VERSION
+ #ifdef _LIBCPP_VERSION
// The iterator statisfies the output_iterator concept but not the
ldionne:
// The iterator statisfies the output_iterator concept but not the
// Cpp17OutputIterator allowing this in <algorithm> is a libc++ extension.
test_int<cpp20_output_iterator<int*> >();
#endif
test_int<forward_iterator<int*> >(); test_int<forward_iterator<int*> >();
test_int<bidirectional_iterator<int*> >(); test_int<bidirectional_iterator<int*> >();
test_int<random_access_iterator<int*> >(); test_int<random_access_iterator<int*> >();
test_int<int*>(); test_int<int*>();
test_int_array(); test_int_array();
test_int_array_struct_source(); test_int_array_struct_source();
test_struct_array(); test_struct_array();
Show All 10 Lines