[libc++] Implement the output_iterator and output_range concepts

[ldionne]

Update RangeStatus paper, and move author to "Various" since they were implemented in various patches by various people.

[• Quuxplusone]

LGTM mod comments.

libcxx/docs/Status/RangesPaper.csv

51

Is iter_value_t in the "dependencies" column? I'd think that things that have been completed don't need to mention their dependencies anymore.
Honestly, things that have been completed don't need to mention their authors anymore; but I know this could be perceived as me complaining about other people getting internet points only because I myself have zero internet points at the moment. ;)

libcxx/include/__iterator/concepts.h

133

As usual, I think it would be nice to use static_cast<_Tp&&>(__t) here, but I don't object if we're not doing that (yet).

libcxx/include/__ranges/concepts.h

96

Might drive-by condense these >>s.

libcxx/include/ranges

71

+2 spaces here to match indentation below

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.output/output_iterator.compile.pass.cpp

51

// Not satisfied when we can't assign a T to the result of *it
would be clearer as re parallel construction with line 39. It took me a while to figure out what was going on here.
Admittedly, that was because I fixated on the void operator++(int) on line 42. Consider making that something like const T *operator++(int) — i.e., you should work in the entire expression *it++ = T(), don't just make *it++ ill-formed by itself.

[Mordante]

Thanks for working on this!
LGTM modulo some nits.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.output/output_iterator.compile.pass.cpp

47

For consistency with the code above, please add a space after the opening parenthesis.

58

For consistency with the code above, please add a space after the opening parenthesis.

[ldionne]

libcxx/include/__iterator/concepts.h

133

We're not. If we do that, we can do it across the library and document it somewhere. I don't want to start doing it as one-offs, since that's just creating inconsistency.

libcxx/include/__ranges/concepts.h

96

Will do in a separate NFC commit.

[ldionne]

Address review comments

[cjdb]

Thanks for implementing this! It somehow slipped by me, but I have two bits of feedback:

• please update all iterator concept conformance tests
• please update all range concept conformance tests

libcxx/docs/Status/RangesPaper.csv

 `[iterator.concepts] <http://wg21.link/iterator.concepts>`_,"| `indirectly_readable <https://llvm.org/D100073>`_
 | `indirectly_writable <https://llvm.org/D100073>`_
 | `weakly_incrementable <https://llvm.org/D100080>`_
 | `incrementable <https://llvm.org/D100080>`_
 | `input_or_output_iterator <https://llvm.org/D100160>`_
 | `sentinel_for <https://llvm.org/D100160>`_
 | `sized_sentinel_for <https://llvm.org/D101371>`_
 | `input_iterator <https://llvm.org/D100271>`_
-| output_iterator
+| `output_iterator <https://llvm.org/D106704>`_
 | `forward_iterator <https://llvm.org/D100275>`_
 | `bidirectional_iterator <https://llvm.org/D100278>`_
 | `random_access_iterator <https://llvm.org/D101316>`_
-| `contiguous_iterator <https://llvm.org/D101396>`_",iter_value_t,Christopher Di Bella,In progress
+| `contiguous_iterator <https://llvm.org/D101396>`_",,Various,✅
 `[indirectcallable.indirectinvocable] <http://wg21.link/indirectcallable.indirectinvocable>`_,"| indirectly_unary_invocable
 | `indirectly_regular_unary_invocable <https://llvm.org/D101277>`_
 | `indirectly_unary_predicate <https://llvm.org/D101277>`_
 | `indirectly_binary_predicate <https://llvm.org/D101277>`_
 | `indirectly_equivalence_relation <https://llvm.org/D101277>`_
 | `indirectly_strict_weak_order <https://llvm.org/D101277>`_",[readable.traits],Louis Dionne,✅
 `[projected] <http://wg21.link/projected>`_,`ranges::projected <https://llvm.org/D101277>`_,[iterator.concepts],Louis Dionne,✅
 `[common.alg.req] <http://wg21.link/common.alg.req>`_: pt. 1,"| `indirectly_movable <https://llvm.org/D102639>`_

 | `ranges::view <https://llvm.org/D101547>`_",[range.range],Louis Dionne,✅
 `[range.refinements] <http://wg21.link/range.refinements>`_,"| ranges::output_range
 | `ranges::input_range <https://llvm.org/D100271>`_
 | `ranges::forward_range: `D100275 <https://llvm.org/D100275>`_
 | `ranges::bidirectional_range <https://llvm.org/D100278>`_
 | `ranges::random_access_range <https://llvm.org/D101316>`_
 | ranges::contiguous_range
 | `ranges::common_range <https://llvm.org/D100269>`_",[range.range],Christopher Di Bella,✅
-`[range.refinements]`_,`ranges::viewable_range <https://reviews.llvm.org/D105816>`_,[range.range],Louis Dionne,✅
+`[range.refinements]`_,`ranges::viewable_range <https://llvm.org/D105816>`_,[range.range],Louis Dionne,✅
 `[range.utility.helpers] <http://wg21.link/range.utility.helpers>`_,"| *simple-view*
 | *has-arrow*
 | *not-same-as*","| [range.range]
 | [iterator.concept.input]",Zoe Carver,✅
 `[view.interface] <http://wg21.link/view.interface>`_,"`ranges::view_interface <https://llvm.org/D101737>`_","| [ranges.range]
 | [range.view]
 | [range.iterator.op.prev]
 | [range.refinements]",Zoe Carver,✅
 `[range.subrange] <http://wg21.link/range.subrange>`_,`ranges::subrange <https://llvm.org/D102006>`_,[view.interface],Zoe Carver,✅
 `[range.dangling] <http://wg21.link/range.dangling>`_,"| ranges::dangling
 | ranges::borrowed_iterator_t
 | ranges::borrowed_subrange_t","| [range.range]
 | [range.subrange]",Christopher Di Bella,✅
 `[range.all] <http://wg21.link/range.all>`_,`view::all <https://llvm.org/D102028>`_,"[range.subrange], [range.view.ref]",Zoe Carver,✅
 `[range.view.ref] <http://wg21.link/range.view>`_,`ref-view <https://llvm.org/D102020>`_,[view.interface],Zoe Carver,✅
 `[range.filter] <http://wg21.link/range.filter>`_,filter_view,[range.all],Louis Dionne,Not started
 `[range.transform] <http://wg21.link/range.transform>`_,`transform_view <https://llvm.org/D103056>`_,[range.all],Zoe Carver,✅
 `[range.iota] <http://wg21.link/range.iota>`_,iota_view,[range.all],Louis Dionne,Not started
 `[range.take] <http://wg21.link/range.take>`_,take_view,[range.all],Zoe Carver,In Progress
 `[range.join] <http://wg21.link/range.join>`_,join_view,[range.all],Christopher Di Bella,Not started
-`[range.empty] <http://wg21.link/range.empty>`_,`empty_view <https://reviews.llvm.org/D103208>`_,[view.interface],Zoe Carver,✅
+`[range.empty] <http://wg21.link/range.empty>`_,`empty_view <https://llvm.org/D103208>`_,[view.interface],Zoe Carver,✅
 `[range.single] <http://wg21.link/range.single>`_,single_view,[view.interface],Zoe Carver,In Progress
 `[range.split] <http://wg21.link/range.split>`_,split_view,[range.all],Unassigned,Not started
 `[range.counted] <http://wg21.link/range.counted>`_,view::counted,[range.subrange],Zoe Carver,Not started
 `[range.common] <http://wg21.link/range.common>`_,common_view,[range.all],Zoe Carver,✅
 `[range.reverse] <http://wg21.link/range.reverse>`_,reverse_view,[range.all],Unassigned,Not started

libcxx/include/__iterator/concepts.h

 // [iterator.concept.input]
 template<class _Ip>
 concept input_iterator =
   input_or_output_iterator<_Ip> &&
   indirectly_readable<_Ip> &&
   requires { typename _ITER_CONCEPT<_Ip>; } &&
   derived_from<_ITER_CONCEPT<_Ip>, input_iterator_tag>;
 
+// [iterator.concept.output]
+template<class _Ip, class _Tp>
+concept output_iterator =
+  input_or_output_iterator<_Ip> &&
+  indirectly_writable<_Ip, _Tp> &&
+  requires (_Ip __it, _Tp&& __t) {
+    *__it++ = _VSTD::forward<_Tp>(__t); // not required to be equality-preserving
+  };
+
 // [iterator.concept.forward]
 template<class _Ip>
 concept forward_iterator =
   input_iterator<_Ip> &&
   derived_from<_ITER_CONCEPT<_Ip>, forward_iterator_tag> &&
   incrementable<_Ip> &&
   sentinel_for<_Ip, _Ip>;
 

libcxx/include/__ranges/concepts.h

namespace ranges {
 
   template<class _Range>
   concept __simple_view =
     view<_Range> && range<const _Range> &&
     same_as<iterator_t<_Range>, iterator_t<const _Range>> &&
     same_as<sentinel_t<_Range>, iterator_t<const _Range>>;
 
   // [range.refinements], other range refinements
+  template <class _Rp, class _Tp>
+  concept output_range = range<_Rp> && output_iterator<iterator_t<_Rp>, _Tp>;
+
   template <class _Tp>
   concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp> >;
 
   template <class _Tp>
   concept forward_range = input_range<_Tp> && forward_iterator<iterator_t<_Tp> >;
 
   template <class _Tp>
   concept bidirectional_range = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp> >;
 
   template <class _Tp>

libcxx/include/iterator

 
 template<class S, class I>
   concept sized_sentinel_for = see below;
 
 // [iterator.concept.input], concept input_iterator
 template<class I>
   concept input_iterator = see below;                      // since C++20
 
+// [iterator.concept.output], concept output_iterator
+template<class I, class T>
+  concept output_iterator = see below;                     // since C++20
+
 // [iterator.concept.forward], concept forward_iterator
 template<class I>
   concept forward_iterator = see below;                    // since C++20
 
 // [iterator.concept.bidir], concept bidirectional_iterator
 template<class I>
   concept bidirectional_iterator = see below;              // since C++20
 

libcxx/include/ranges

template<class T>
     inline constexpr bool enable_view = ...;
 
   struct view_base { };
 
   template<class T>
     concept view = ...;
 
   // [range.refinements], other range refinements
+  template<class R, class T>
+    concept output_range = see below;
+
   template<class T>
     concept input_range = see below;
 
   template<class T>
     concept forward_range = see below;
 
   template<class T>
   concept bidirectional_range = see below;

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.output/output_iterator.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// template<class It, class T>
+// concept output_iterator;
+
+#include <iterator>
+
+#include <cstddef>
+#include "test_iterators.h"
+
+struct T { };
+struct DerivedFromT : T { };
+
+static_assert( std::output_iterator<output_iterator<int*>, int>);
+static_assert( std::output_iterator<output_iterator<int*>, short>);
+static_assert( std::output_iterator<output_iterator<int*>, long>);
+static_assert( std::output_iterator<output_iterator<T*>, T>);
+static_assert(!std::output_iterator<output_iterator<T const*>, T>);
+static_assert( std::output_iterator<output_iterator<T*>, T const>);
+static_assert( std::output_iterator<output_iterator<T*>, DerivedFromT>);
+static_assert(!std::output_iterator<output_iterator<DerivedFromT*>, T>);
+
+// Not satisfied when the iterator is not an input_or_output_iterator
+static_assert(!std::output_iterator<void, int>);
+static_assert(!std::output_iterator<void (*)(), int>);
+static_assert(!std::output_iterator<int&, int>);
+static_assert(!std::output_iterator<T, int>);
+
+// Not satisfied when we can't assign a T to the result of *it++
+struct WrongPostIncrement {
+    using difference_type = std::ptrdiff_t;
+    T const* operator++(int);
+    WrongPostIncrement& operator++();
+    T& operator*();
+};
+static_assert( std::input_or_output_iterator<WrongPostIncrement>);
+static_assert( std::indirectly_writable<WrongPostIncrement, T>);
+static_assert(!std::output_iterator<WrongPostIncrement, T>);
+
+// Not satisfied when we can't assign a T to the result of *it (i.e. not indirectly_writable)
+struct NotIndirectlyWritable {
+    using difference_type = std::ptrdiff_t;
+    T* operator++(int);
+    NotIndirectlyWritable& operator++();
+    T const& operator*(); // const so we can't write to it
+};
+static_assert( std::input_or_output_iterator<NotIndirectlyWritable>);
+static_assert(!std::indirectly_writable<NotIndirectlyWritable, T>);
+static_assert(!std::output_iterator<NotIndirectlyWritable, T>);

libcxx/test/std/ranges/range.req/range.refinements/output_range.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// template<class R, class T>
+// concept output_range;
+
+#include <ranges>
+
+#include <iterator>
+#include "test_iterators.h"
+#include "test_range.h"
+
+struct T { };
+
+// Satisfied when it's a range and has the right iterator
+struct GoodRange {
+    output_iterator<T*> begin();
+    sentinel end();
+};
+static_assert(std::ranges::range<GoodRange>);
+static_assert(std::output_iterator<std::ranges::iterator_t<GoodRange>, T>);
+static_assert(std::ranges::output_range<GoodRange, T>);
+
+// Not satisfied when it's not a range
+struct NotRange {
+    output_iterator<T*> begin();
+};
+static_assert(!std::ranges::range<NotRange>);
+static_assert( std::output_iterator<std::ranges::iterator_t<NotRange>, T>);
+static_assert(!std::ranges::output_range<NotRange, T>);
+
+// Not satisfied when the iterator is not an output_iterator
+struct RangeWithBadIterator {
+    cpp17_input_iterator<T const*> begin();
+    sentinel end();
+};
+static_assert( std::ranges::range<RangeWithBadIterator>);
+static_assert(!std::output_iterator<std::ranges::iterator_t<RangeWithBadIterator>, T>);
+static_assert(!std::ranges::output_range<RangeWithBadIterator, T>);