[libcxx] Define insert_iterator::iter with ranges::iterator_t

[• Quuxplusone]

Summary

insert_iterator::iter member object is defined as Container::iterator but
the standard requires iter to be defined in terms of ranges::iterator_t as
of C++20. So, if in C++20 or later, define iter member object as
ranges::iterator_t.

[cjdb]

Please add a unit test, then I'll LGTM.

[• Quuxplusone]

Also LGTM % lack of test. The new test should use a simple custom container that has a ranges::iterator_t but no nested ::iterator type. The only member function your custom container needs to provide is .insert.

libcxx/include/__iterator/insert_iterator.h

21–23

Our preferred style here is to #include <__ranges/access.h> unconditionally, alphabetized among the above headers. If !(_LIBCPP_STD_VER > 17), this #include will just be a no-op, and that's fine.

(Compare #include <__iterator/iterator.h> on line 14: that type is used on line 37 only if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES), but we don't guard line 14, only line 37.)

[jloser]

Unconditionally include <__ranges/access.h>

[ldionne]

Thanks for fixing this! As others have mentioned, please add a short test for this and I think it should be good to go.

libcxx/include/__iterator/insert_iterator.h

46

That should fix the CI issues you're seeing.

In the not-too-far future, we'll be able to drop _LIBCPP_HAS_NO_RANGES altogether, but for now we still support 1-2 compilers that don't implement concepts, and hence on which Ranges are not available.

[jloser]

Add test for type without iterator type alias

[jloser]

libcxx/include/__iterator/insert_iterator.h

58

@cjdb @ldionne @Quuxplusone this is a drive-by fix so that the constructor of insert_iterator matches the iter type declared as the protected member. Do we like using decltype(iter) here so it's correct in both cases or would we prefer an #ifdef here like we do when defining the iter member?

[jloser]

@ldionne @Quuxplusone @cjdb - added a test for a type without a nested iterator type alias to exercise the defining of iter member using std::ranges::iterator_t. Please me know what you think. Thanks!

[• Quuxplusone]

libcxx/include/__iterator/insert_iterator.h

58

decltype(iter) seems fine to me. (This is a good catch! The new test achieved its goal!)

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/types.pass.cpp

31 ↗

(On Diff #368547)

This should be #include <ranges> if you need it at all; but you don't.

79–96 ↗

(On Diff #368547)

Lines 79–96 belong outside of the main function. Also, you're using vector instead of a custom container, you seem to be confusing container and value throughout, and you've given your "container" an insert method that returns an insert_iterator. Instead of all that, I suggest that you use something like the following code:

struct NoIteratorAlias {
    long data_[3] = {};
    using value_type = int;
    long *begin() { return nullptr; }
    constexpr long *insert(long *pos, int value) { *pos = value; return pos; }
};

#if TEST_STD_VER > 17
constexpr bool test_no_iterator_alias()
{
    NoIteratorAlias c;
    auto it = std::insert_iterator<NoIteratorAlias>(c, c.data_);
    *it++ = 1;
    *it++ = 2;
    assert(c.data_[0] == 1);
    assert(c.data_[1] == 2);
    assert(c.data_[2] == 0);
}
#endif // TEST_STD_VER > 17

int main(int, char**)
{
    test<std::vector<int> >();

#if TEST_STD_VER > 17
    test<NoIteratorAlias>();
    test_no_iterator_alias();
    static_assert(test_no_iterator_alias());
#endif // TEST_STD_VER > 17
}

This involves testing not just the existence of the typedefs but also the runtime behavior of the insert_iterator. I believe we currently have separate test files for those two things. So, either modify both test files, or create one new test file specifically for this feature. (The latter approach has the benefit that you can UNSUPPORTED that new test file pre-C++20 and/or when Ranges is not supported.)

[ldionne]

LGTM with my and Arthur's comments applied, and CI passing.

Arthur, I'll let you give the final approval.

libcxx/include/__iterator/insert_iterator.h

50

You can remove this comment - the #if is so small that we can easily see the condition when looking at the #endif.

[jloser]

Simplify test per Arthur's suggestions

[jloser]

Remove #ifdef comment in insert_iterator.h

[jloser]

libcxx/include/__iterator/insert_iterator.h

50

Just removed it. I saw the comment on #endif in other files which is why I wrote that. Do we typically only write a comment if the #ifdef is long (i.e. the #endif is far from the starting #ifdef)?

[jloser]

Remove #ifdef comment in test

[jloser]

Avoid using decltype(iter) in insert_iterator constructor since this file may be included in C++03 mode and decltype specifier only works in C++11 or later.

[jloser]

Split out testing iter member in C++20 into a seprate test file to avoid #ifdefs everywhere

[• Quuxplusone]

libcxx/include/__iterator/insert_iterator.h

43–47

It would probably be better to introduce a private typedef __iterator to avoid repeating the ifdefs:

_LIBCPP_SUPPRESS_DEPRECATED_POP
#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_RANGES)
    typedef ranges::iterator_t<_Container> __iterator_type;
#else
    typedef typename _Container::iterator __iterator_type;
#endif
protected:
    _Container* container;
    __iterator_type iter;
~~~
    _LIBCPP_INLINE_VISIBILITY constexpr insert_iterator(_Container& __x, __iterator_type __i)
        : container(_VSTD::addressof(__x)), iter(__i) {}

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/cxx20_iter_member.pass.cpp

20

I think we can omit the body of begin(), actually. Just long *begin(); should be good enough.
(I'd originally been giving it a body because I saw it was going to be called from test<NoIteratorAlias>(); but then I decided not to bother calling test<NoIteratorAlias>() after all.)
Also, yikes! You've lost the distinction between value_type=int and ranges::iterator_t<NoIteratorAlias>=long*, which, remember, is the entire point of this test.

But this has given me time to realize that we can do even better with the test. Leave value_type as int, but change the iterator type by making it float *begin() and float data_[4]...

Actually, let me just commandeer this.

[• Quuxplusone]

Commandeered to update the test file. Also, update std::inserter for C++20 at the same time.

[• Quuxplusone]

Flip the arguments to ASSERT_SAME_TYPE. Add a comment. NFC.

@ldionne, since I updated this significantly, I'm kicking it back to you for final approval. :)

[jloser]

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/cxx20_iter_member.pass.cpp

40

Should we just use static_assert with std::is_same_v since this test file only supports C++20 anyway (meaning there isn't a need to route through ASSERT_SAME_TYPE)?

[• Quuxplusone]

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/cxx20_iter_member.pass.cpp

40

I think the question is not quite settled globally, but personally, I prefer ASSERT_SAME_TYPE because

• it is shorter, and
• it "always works" — doesn't require making any judgment calls about which C++ versions the test supports — and
• it won't require refactoring five years down the road when the test gets extended to other C++ versions (this happens more often than you might think).

Hypothetically, if we were to go the "always use the latest and greatest possible, no software-engineering considerations" route, then we'd also have to consider static_assert with std::same_as ("since this test file only supports C++20 with concepts+ranges anyway").

[jloser]

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/cxx20_iter_member.pass.cpp

20

Oops, sorry I mixed up the distinction between the value_type and the iter type from ranges::iterator_t when I split this into a separate test file. Also, good point about only needing a declaration for begin and not a definition now.

Thanks for taking over this work and cleaning it up. I appreciate your comments and patience with me on this review as I'm starting to get my feet wet in libc++.

[cjdb]

This looks like it's ready to rock as-is. The only comment of mine that's blocking is the one addressing diagnostic concerns.

libcxx/include/__iterator/insert_iterator.h

58

Do we like using decltype(iter) here so it's correct in both cases or would we prefer an #ifdef here like we do when defining the iter member?

If this isn't public: have at it. If it is public: please use something that will produce the most meaningful diagnostic to the user.

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/cxx20_iter_member.pass.cpp

34

Let's use constructible_from since it's also got a destructible sanity check.

40

Unless you're intentionally directly testing the constructor on line 38, the way in which I'd write this is

std::same_as<std::insert_iterator<NoIteratorAlias>> auto it = std::insterer(c, c.data_);

[ldionne]

LGTM with my comments applied.

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/cxx20_iter_member.pass.cpp

14

Please add a comment explaining what this is testing. Something like Make sure we use ranges::iterator_t instead of Container::iterator in C++20 and above.

36

More consistent with what we usually do.

[• Quuxplusone]

libcxx/include/__iterator/insert_iterator.h

58

This is how it looks after the PR:

x.cpp:7:39: error: no matching constructor for initialization of 'std::insert_iterator<decltype(v)>' (aka 'insert_iterator<vector<int>>')
    std::insert_iterator<decltype(v)> it(v, w.begin());
                                      ^  ~~~~~~~~~~~~
build2/include/c++/v1/__iterator/insert_iterator.h:58:61: note: candidate constructor not viable: no known conversion from 'std::vector<double>::iterator' (aka '__wrap_iter<double *>') to '__insert_iterator_iter_t<std::vector<int>>' (aka 'std::__wrap_iter<int *>') for 2nd argument
    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator(_Container& __x, __insert_iterator_iter_t<_Container> __i)
                                                            ^

compared to before:

x.cpp:7:39: error: no matching constructor for initialization of 'std::insert_iterator<decltype(v)>' (aka 'insert_iterator<vector<int>>')
    std::insert_iterator<decltype(v)> it(v, w.begin());
                                      ^  ~~~~~~~~~~~~
build/include/c++/v1/__iterator/insert_iterator.h:52:61: note: candidate constructor not viable: no known conversion from '__wrap_iter<std::vector<double>::pointer>' to '__wrap_iter<std::vector<int>::pointer>' for 2nd argument
    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator(_Container& __x, typename _Container::iterator __i)
                                                            ^

I call this "no significant difference in awfulness."

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/cxx20_iter_member.pass.cpp

34

This assertion is just sanity-checking that NoIteratorAlias is not constructible from int*, because if it were constructible from int*, then that would nerf the whole point of the test (which is to verify that insert_iterator doesn't accidentally try to construct it from int* instead of double*). Destructibility is irrelevant.

libcxx/include/__iterator/insert_iterator.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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___ITERATOR_INSERT_ITERATOR_H
 #define _LIBCPP___ITERATOR_INSERT_ITERATOR_H
 
 #include <__config>
 #include <__iterator/iterator.h>
 #include <__iterator/iterator_traits.h>
 #include <__memory/addressof.h>
+#include <__ranges/access.h>
 #include <__utility/move.h>
 #include <cstddef>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_RANGES)
+template <class _Container>
+using __insert_iterator_iter_t = ranges::iterator_t<_Container>;
+#else
+template <class _Container>
+using __insert_iterator_iter_t = typename _Container::iterator;
+#endif
+
 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
 template <class _Container>
 class _LIBCPP_TEMPLATE_VIS insert_iterator
 #if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES)
     : public iterator<output_iterator_tag, void, void, void, void>
 #endif
 {
 _LIBCPP_SUPPRESS_DEPRECATED_POP
 protected:
     _Container* container;
-    typename _Container::iterator iter; // FIXME: `ranges::iterator_t<Container>` in C++20 mode
+    __insert_iterator_iter_t<_Container> iter;
 public:
     typedef output_iterator_tag iterator_category;
     typedef void value_type;
 #if _LIBCPP_STD_VER > 17
     typedef ptrdiff_t difference_type;
 #else
     typedef void difference_type;
 #endif
     typedef void pointer;
     typedef void reference;
     typedef _Container container_type;
 
-    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator(_Container& __x, typename _Container::iterator __i)
+    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator(_Container& __x, __insert_iterator_iter_t<_Container> __i)
         : container(_VSTD::addressof(__x)), iter(__i) {}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator=(const typename _Container::value_type& __value_)
         {iter = container->insert(iter, __value_); ++iter; return *this;}
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator=(typename _Container::value_type&& __value_)
         {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;}
 #endif // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator*()        {return *this;}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator++()       {return *this;}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator++(int)    {return *this;}
 };
 
 template <class _Container>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 insert_iterator<_Container>
-inserter(_Container& __x, typename _Container::iterator __i)
+inserter(_Container& __x, __insert_iterator_iter_t<_Container> __i)
 {
     return insert_iterator<_Container>(__x, __i);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_INSERT_ITERATOR_H

libcxx/test/std/iterators/predef.iterators/insert.iterators/insert.iterator/cxx20_iter_member.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: libcpp-has-no-incomplete-ranges
+
+// insert_iterator
+// C++20 and above use ranges::iterator_t<Container> instead of Container::iterator.
+
+#include <iterator>
+
+#include <cassert>
+#include <type_traits>
+
+#include "test_macros.h"
+
+struct NoIteratorAlias {
+    double data_[3] = {};
+    using value_type = int;
+    double *begin();
+    constexpr double *insert(double *pos, int value) {
+        *pos = value;
+        return pos;
+    }
+};
+
+static_assert(std::is_constructible_v<std::insert_iterator<NoIteratorAlias>, NoIteratorAlias&, double*>);
+static_assert(!std::is_constructible_v<std::insert_iterator<NoIteratorAlias>, NoIteratorAlias&, int*>);
+
+constexpr bool test() {
+    NoIteratorAlias c;
+    double half = 0.5;
+    auto it = std::insert_iterator<NoIteratorAlias>(c, c.data_);
+    ASSERT_SAME_TYPE(decltype(std::inserter(c, c.data_)), std::insert_iterator<NoIteratorAlias>);
+    *it++ = 1 + half;  // test that RHS is still implicitly converted to _Container::value_type
+    *it++ = 2 + half;
+    assert(c.data_[0] == 1.0);
+    assert(c.data_[1] == 2.0);
+    assert(c.data_[2] == 0.0);
+    return true;
+}
+
+int main(int, char**) {
+    test();
+    static_assert(test());
+
+    return 0;
+}