[libc++] Fix common_iterator for output_iterators

[ldionne]

Summary

We were missing a constraint in common_iterator's iterator_traits and
we were eagerly instantiating iter_value_t even when invalid.

Thanks to Casey Carter for finding this bug.

[• Quuxplusone]

Nice catch! That test is a mess, though. I don't object to landing this as-is, just to fix the bug; I would also be happy to merge it into D117400. Your call.

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

55

Well this is weird. non_const_deref_iterator<int*>::iterator_category appears to be input_iterator_tag, but std::common_iterator<Iter, sentinel_type<int*>> is an output iterator instead?

Also, I'm seeing now that non_const_deref_iterator is a template, but it's used in only one place (with int*), so it can be massively simplified. Would you like me to just take this over and merge it into my existing D117400?

[ldionne]

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

55

Yeah, I'd like to understand this part as well.

[CaseyCarter]

I don't object to landing this as-is, just to fix the bug; I would also be happy to merge it into D117400. Your call.

I have a mild preference to merge this small fix as-is.

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

55

input_iterator requires that const iterators are dereferenceable. Hopefully it's obvious that is not the case for non_const_deref_iterator, so it does not trigger the iterator_traits<common_iterator<I, S>> partial specialization once that partial specialization is properly constrained to require input_iterator.

[• Quuxplusone]

@ldionne rubberstamp here as-is, and revisit in D117400? :)

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

55

I get everything you said, but I still don't get why "Iter doesn't satisfy input_iterator" should lead us to "iterator_traits<CommonIter>::iterator_category is defined and is equal to output_iterator_tag." Like, Iter isn't an output iterator either... is it? So the most logical outcomes (in increasing order of wild-west-ness) would have been for CommonIter to be ill-formed, or for CommonIter to be well-formed but not an iterator, or for iterator_traits<CommonIter>::iterator_category to be defined as equal to iterator_traits<Iter>::iterator_category. Having it just randomly equal to output_iterator_tag seems bizarre!

(I'm not disputing that it's probably correct according to C++20; I'm just confused about both the mental model and, literally, I don't see by what codepath we end up with output_iterator_tag. Not that I've looked hard at all.)

[ldionne]

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

55

Thanks for explaining @CaseyCarter , but in that case I fail to see the point of this test at all. Instead, why don't we use common_iterator with an output_iterator, and then simply check that IterTraits::iterator_concept isn't defined (which would effectively be a regression test for your change). In other words:

using Iter = output_iterator<int*>;
using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
using IterTraits = std::iterator_traits<CommonIter>;

static_assert(!HasIteratorConcept<IterTraits>);
static_assert(std::same_as<IterTraits::iterator_category, std::output_iterator_tag>);
// etc...

Do you agree that is what we want? Note that this won't work today because it appears that common_iterator<output_iterator<int*>> doesn't work at all today, but we can and should fix that separately (I have a WIP patch locally).

[ldionne]

Commandeering to fix common_iterator with output_iterator. I would have done it as part of a separate patch, but both are interdependent (I can't write tests for my part of the change without your changes).

[ldionne]

Fix common_iterator for output_iterator. Do you folks agree this is the right direction?

[• Quuxplusone]

I continue to think all of these directions are better than the status quo. Consider me still "accept"ing.

libcxx/include/__iterator/common_iterator.h

34–36

Nit: Did you add line 34 to avoid prematurely instantiating iter_reference_t? Is it possible to regression-test for that? Should we? If removing line 34 would be conforming, I'd just do that.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

87–88 ↗

(On Diff #400874)

154–155 ↗

(On Diff #400874)

IIUC this comment is misleading. iter_value_t for an ordinary C++11 output iterator is just ThatType::value_type. It's only if the iterator doesn't define a value_type, or defines it as a non-object type, that iter_value_t might be ill-formed.
https://godbolt.org/z/1Ybjv7o9G
Our test iterator's output_iterator<int*>::value_type is void, so its iter_value_t is indeed ill-formed, but that's a special property of our output_iterator, not all output iterators in general.

I'd like to see test coverage for "output iterator with valid value_type" added to iterator_traits.compile.pass.cpp above, even if this means defining a little helper type a la the OutIt in my godbolt.

174 ↗

(On Diff #400874)

Consider checking iter != sent on at least one of the previous lines.

[CaseyCarter]

LGTM, with Arthur's comments. (Although I'm fine with the extra typename requirement in __can_use_postfix_proxy.)

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

55

common_iterator assumes that non-input_iterators must be output_iterators. Testing with non_const_deref_iterator is equivalent to testing with output_iterator if we never dereference an iterator. common_iterator doesn't intend to be as general as possible: it exists only to adapt "new" iterator+sentinels into "old" iterator pairs. Consequently it has little patience with types that don't satisfy the concepts.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

154–155 ↗

(On Diff #400874)

"need not be valid for output iterators" would be fine here.

[ldionne]

Apply review comments.

libcxx/include/__iterator/common_iterator.h

34–36

No, the constraint was redundant with simply using iter_value_t in the expressions themselves. Removed.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

154–155 ↗

(On Diff #400874)

Agreed, the comment was wrong, I'll fix it. However:

I'd like to see test coverage for "output iterator with valid value_type" added to iterator_traits.compile.pass.cpp above, even if this means defining a little helper type a la the OutIt in my godbolt.

The problem is that even though iter_value_t<OutputIter> *can* be non-void, iter_value_t<common_iterator<OutputIter>> will never be, because we are now properly constraining the iterator_traits<common_iterator<...>> specialization to only work on input_iterators. So I can't add a test that checks that iter_value_t<common_iterator<OutputIter>> is going to be non-void.

Please LMK if you think I'm mistaken here.

[• Quuxplusone]

I assume this is still OK, and still necessary, even after D117400 which I assume must have merge-conflicted with it a lot?

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

154–155 ↗

(On Diff #400874)

I haven't investigated so I assume you're not mistaken. Then it just sounds like my request shifts from test coverage for common_iterator<OutputIterWithNonVoidValueType>::iterator_category, to test coverage that common_iterator<OutputIterWithNonVoidValueType> is SFINAE-friendly ill-formed. I believe we have some prior art, shaped roughly like

template<class T>
concept HasCommonIterator = requires { typename std::ranges::common_iterator<T>; };
static_assert(!HasCommonIterator<OutputIterWithNonVoidValueType>);

[ldionne]

Add test.

[ldionne]

In D117449#3270076, @Quuxplusone wrote:

I assume this is still OK, and still necessary, even after D117400 which I assume must have merge-conflicted with it a lot?

Yes, still necessary. There were only small merge conflicts.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

154–155 ↗

(On Diff #400874)

I'm not following. common_iterator<OutputIterWithNonVoidValueType> does work, it's only that you can't query its iterator_traits.

I added a test in iterator_traits.compile.pass.cpp which isn't the most useful (because it ends up basically testing the iterator_traits base template), but should clarify what I mean.

[ldionne]

Will ship once CI passes unless @Quuxplusone has other comments.

[• Quuxplusone]

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

154–155 ↗

(On Diff #400874)

I'm not following. common_iterator<OutputIterWithNonVoidValueType> does work, it's only that you can't query its iterator_traits.

Well, now I'm confused. How can you have an iterator, that "works," but you can't query its iterator_traits? What does that even mean? I would think that by definition a "working iterator" must have iterator_traits that say it's an iterator. Otherwise it's not an iterator.

I pasted your NonVoidOutputIterator into a Godbolt; what happens after this patch? (Also I assume that spew on GCC indicates a libstdc++ bug @jwakely.) https://godbolt.org/z/KrxY6Wd97
I'm surprised that common_iterator<OI, ...>::value_type is void instead of OI::value_type, but I think that's what the standard literally says, yeah.

[ldionne]

The CI only failed on Windows due to missing space. I'm going to ship this now, and we can make adjustments post-commit if the discussion ends up bringing up additional issues.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

154–155 ↗

(On Diff #400874)

Sorry, I should have been precise. I don't mean that iterator_traits<common_iterator<OutputIterWithNonVoidValueType>> doesn't work. I mean that iterator_traits<common_iterator<OutputIterWithNonVoidValueType>>::value_type is void, despite OutputIterWithNonVoidValueType::value_type not being void. And yes, I think it's a bit silly, but it's definitely what the Standard says.

The reason is simply that iterator_traits<common_iterator<It>> requires It to be an input_iterator. If it is, then the value_type is properly forwarded through. If it isn't, then we end up falling back on the base template of iterator_traits (https://en.cppreference.com/w/cpp/iterator/iterator_traits):

Otherwise, if Iter satisfies the exposition-only concept __LegacyIterator, the member types are declared as follows:

Member type         Definition
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
difference_type     std::incrementable_traits<Iter>::difference_type if valid, otherwise void
value_type          void
pointer             void
reference           void
iterator_category   std::output_iterator_tag

That's my understanding anyways.

libcxx/include/__iterator/common_iterator.h

 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
 template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
   requires (!same_as<_Iter, _Sent> && copyable<_Iter>)
 class common_iterator {
   class __proxy {
     friend common_iterator;
 
     iter_value_t<_Iter> __value;
     // We can move __x because the only caller verifies that __x is not a reference.
     constexpr __proxy(iter_reference_t<_Iter>&& __x)
       : __value(_VSTD::move(__x)) {}
 
   public:
     const iter_value_t<_Iter>* operator->() const {

 };
 
 template<class _Iter, class _Sent>
   requires __common_iter_has_ptr_op<_Iter, _Sent>
 struct __arrow_type_or_void<_Iter, _Sent> {
     using type = decltype(declval<const common_iterator<_Iter, _Sent>>().operator->());
 };
 
-template<class _Iter, class _Sent>
+template<input_iterator _Iter, class _Sent>
 struct iterator_traits<common_iterator<_Iter, _Sent>> {
   using iterator_concept = _If<forward_iterator<_Iter>,
                                forward_iterator_tag,
                                input_iterator_tag>;
   using iterator_category = _If<__denotes_forward_iter<_Iter>,
                                 forward_iterator_tag,
                                 input_iterator_tag>;
   using pointer = typename __arrow_type_or_void<_Iter, _Sent>::type;

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

 // template<input_iterator I, class S>
 //   struct iterator_traits<common_iterator<I, S>>;
 
 #include <iterator>
 
 #include "test_macros.h"
 #include "types.h"
 
+template<class T>
+concept HasIteratorConcept = requires { typename T::iterator_concept; };
+
 void test() {
   {
     using Iter = simple_iterator<int*>;
     using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
     using IterTraits = std::iterator_traits<CommonIter>;
 
     static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
     static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);
void test() {
     static_assert(!std::same_as<IterTraits::pointer, int*>);
     static_assert(std::same_as<IterTraits::reference, int>);
   }
   {
     using Iter = non_const_deref_iterator<int*>;
     using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
     using IterTraits = std::iterator_traits<CommonIter>;
 
-    static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
-    static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);
-    static_assert(std::same_as<IterTraits::value_type, int>);
+    static_assert(!HasIteratorConcept<IterTraits>);
+    static_assert(std::same_as<IterTraits::iterator_category, std::output_iterator_tag>);
+    static_assert(std::same_as<IterTraits::value_type, void>);
     static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
     static_assert(std::same_as<IterTraits::pointer, void>);
-    static_assert(std::same_as<IterTraits::reference, int&>);
+    static_assert(std::same_as<IterTraits::reference, void>);
   }
   {
     using Iter = cpp17_input_iterator<int*>;
     using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
     using IterTraits = std::iterator_traits<CommonIter>;
 
     static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
     static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);