[libcxx][iterator] adds `std::input_or_output_iterator` and `std::sentinel_for`

[cjdb]

Summary

Implements parts of:

• P0896R4 The One Ranges Proposal`

Depends on D100080

[cjdb]

updates synopsis, rebases to activate CI

[cjdb]

adds subsumption test

[miscco]

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.sentinel/sentinel_for.compile.pass.cpp

45–49

semi_regular also requires copyability (https://eel.is/c++draft/concepts.object). Please add a check that a non copyable iterator is not a sentinel for itself (aka move-only input iterators)

[zoecarver]

LGMT.

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

186

I'm not going to keep commenting on this if I see it again.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.sentinel/sentinel_for.compile.pass.cpp

45–49

+1

[cjdb]

rebases to activate CI

[Mordante]

In general LGTM modulo some nits and the request of @miscco. But I like to know more about the locale_dependent test before approving.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.sentinel/sentinel_for.compile.pass.cpp

13

Please update this part to template<class S, class I>

102

Here iterator and const_iterator are not tested against the full set, like reverse_iterator and const_reverse_iterator. Can you add them for completeness?

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/locale_dependent.compile.pass.cpp

12

What's locale dependent with this test?
If it's locale dependent it should contain a line // UNSUPPORTED: libcpp-has-no-localization

21

Please remove the sized_sentinel since it isn't added here.

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[ldionne]

Requesting changes until my and other reviewer's comments have been address, to help keep track of the status of this patch.

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

65

Why do we have those here if we also have the various iterator_concept_conformance.compile.pass.cpp tests?

[cjdb]

rebases to activate CI

[cjdb]

applies feedback

[cjdb]

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

65

I mustn't have deleted these before pushing :S
Deleted.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.sentinel/sentinel_for.compile.pass.cpp

102

PTAL at the individual tests.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/locale_dependent.compile.pass.cpp

12

File deleted.

[ldionne]

LGTM with @Mordante 's comment fixed and CI passing. Thanks!

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

54–71

It's not clear to me that testing *all* of those qualifiers adds that much value over just testing one of them. Non-blocking, but if I had written this myself, I wouldn't have tested all of them since it feels like diminishing returns to me.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.sentinel/sentinel_for.compile.pass.cpp

13

You seem to have missed this comment.

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[Mordante]

LGTM, but please address the two minor issues before landing https://reviews.llvm.org/D100160#inline-951054 and the comment below.
And please wait for the CI to turn green.

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/locale_dependent.compile.pass.cpp

21

I still see this comment.

[cjdb]

rebases to activate CI

[cjdb]

• finally applies @ldionne and @Mordante's feedback

libcxx/include/iterator

 // [iterator.concept.winc], concept weakly_­incrementable
 template<class I>
   concept weakly_incrementable = see below;                // since C++20
 
 // [iterator.concept.inc], concept incrementable
 template<class I>
   concept incrementable = see below;                       // since C++20
 
+// [iterator.concept.iterator], concept input_­or_­output_­iterator
+  template<class I>
+    concept input_or_output_iterator = see below;          // since C++20
+
+// [iterator.concept.sentinel], concept sentinel_­for
+template<class S, class I>
+  concept sentinel_for = see below;                        // since C++20
+
 template<class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
 struct iterator
 {
     typedef T         value_type;
     typedef Distance  difference_type;
     typedef Pointer   pointer;
     typedef Reference reference;

 template<class _Ip>
 concept incrementable =
   regular<_Ip> &&
   weakly_incrementable<_Ip> &&
   requires(_Ip __i) {
     { __i++ } -> same_as<_Ip>;
   };
 
-// [iterator.concept.inc]
+// [iterator.concept.iterator]
+template<class _Ip>
+concept input_or_output_iterator =
+  requires(_Ip __i) {
+    { *__i } -> __referenceable;
+  } &&
+  weakly_incrementable<_Ip>;
+
+// [iterator.concept.sentinel]
+template<class _Sp, class _Ip>
+concept sentinel_for =
+  semiregular<_Sp> &&
+  input_or_output_iterator<_Ip> &&
+  __weakly_equality_comparable_with<_Sp, _Ip>;
 
 #undef _LIBCPP_NOEXCEPT_RETURN
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif  // _LIBCPP_ITERATOR

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.iterator/input_or_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 In>
+// concept input_or_output_iterator;
+
+#include <iterator>
+
+#include <array>
+#include <concepts>
+#include <deque>
+#ifndef _LIBCPP_HAS_NO_FILESYSTEM_LIBRARY
+#include <filesystem>
+#endif
+#include <forward_list>
+#include <list>
+#include <map>
+#include <memory>
+#include <set>
+#include <string>
+#include <string_view>
+#include <optional>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+struct missing_dereference {
+  using difference_type = std::ptrdiff_t;
+
+  missing_dereference& operator++();
+  missing_dereference& operator++(int);
+};
+static_assert(std::weakly_incrementable<missing_dereference> && !std::input_or_output_iterator<missing_dereference>);
+
+struct void_dereference {
+  using difference_type = std::ptrdiff_t;
+
+  void operator*();
+  void_dereference& operator++();
+  void_dereference& operator++(int);
+};
+static_assert(std::weakly_incrementable<void_dereference> && !std::input_or_output_iterator<void_dereference>);
+
+struct not_weakly_incrementable {
+  int operator*() const;
+};
+static_assert(!std::input_or_output_iterator<not_weakly_incrementable>);
+
+namespace standard_types {
+static_assert(std::input_or_output_iterator<int*>);
+static_assert(std::input_or_output_iterator<int const*>);
+static_assert(std::input_or_output_iterator<int volatile*>);
+static_assert(std::input_or_output_iterator<int const volatile*>);
+
+// <array>
+static_assert(std::input_or_output_iterator<std::array<int, 10>::iterator>);
+static_assert(std::input_or_output_iterator<std::array<int, 10>::const_iterator>);
+static_assert(std::input_or_output_iterator<std::array<int, 10>::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::array<int, 10>::const_reverse_iterator>);
+
+// <deque>
+static_assert(std::input_or_output_iterator<std::deque<int>::iterator>);
+static_assert(std::input_or_output_iterator<std::deque<int>::const_iterator>);
+static_assert(std::input_or_output_iterator<std::deque<int>::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::deque<int>::const_reverse_iterator>);
+
+// <filesystem>
+#ifndef _LIBCPP_HAS_NO_FILESYSTEM_LIBRARY
+static_assert(std::input_or_output_iterator<std::filesystem::directory_iterator>);
+static_assert(std::input_or_output_iterator<std::filesystem::recursive_directory_iterator>);
+#endif
+
+// <forward_list>
+static_assert(std::input_or_output_iterator<std::forward_list<int>::iterator>);
+static_assert(std::input_or_output_iterator<std::forward_list<int>::const_iterator>);
+
+// <iterator>
+static_assert(!std::input_or_output_iterator<std::back_insert_iterator<std::vector<int> > >);
+static_assert(!std::input_or_output_iterator<std::front_insert_iterator<std::deque<int> > >);
+static_assert(!std::input_or_output_iterator<std::insert_iterator<std::deque<int> > >);
+static_assert(std::input_or_output_iterator<std::move_iterator<std::vector<int>::iterator> >);
+
+// <list>
+static_assert(std::input_or_output_iterator<std::list<int>::iterator>);
+static_assert(std::input_or_output_iterator<std::list<int>::const_iterator>);
+static_assert(std::input_or_output_iterator<std::list<int>::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::list<int>::const_reverse_iterator>);
+
+// <map>
+static_assert(std::input_or_output_iterator<std::map<int, int>::iterator>);
+static_assert(std::input_or_output_iterator<std::map<int, int>::const_iterator>);
+static_assert(std::input_or_output_iterator<std::map<int, int>::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::map<int, int>::const_reverse_iterator>);
+
+static_assert(std::input_or_output_iterator<std::multimap<int, int>::iterator>);
+static_assert(std::input_or_output_iterator<std::multimap<int, int>::const_iterator>);
+static_assert(std::input_or_output_iterator<std::multimap<int, int>::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::multimap<int, int>::const_reverse_iterator>);
+
+// <memory>
+static_assert(!std::input_or_output_iterator<std::shared_ptr<int> >);
+static_assert(!std::input_or_output_iterator<std::shared_ptr<void> >);
+static_assert(!std::input_or_output_iterator<std::unique_ptr<int> >);
+static_assert(!std::input_or_output_iterator<std::unique_ptr<void> >);
+
+// <optional>
+static_assert(!std::input_or_output_iterator<std::optional<int> >);
+
+// <set>
+static_assert(std::input_or_output_iterator<std::set<int>::iterator>);
+static_assert(std::input_or_output_iterator<std::set<int>::const_iterator>);
+static_assert(std::input_or_output_iterator<std::set<int>::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::set<int>::const_reverse_iterator>);
+
+static_assert(std::input_or_output_iterator<std::multiset<int>::iterator>);
+static_assert(std::input_or_output_iterator<std::multiset<int>::const_iterator>);
+static_assert(std::input_or_output_iterator<std::multiset<int>::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::multiset<int>::const_reverse_iterator>);
+
+// <string>
+static_assert(std::input_or_output_iterator<std::string::iterator>);
+static_assert(std::input_or_output_iterator<std::string::const_iterator>);
+static_assert(std::input_or_output_iterator<std::string::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::string::const_reverse_iterator>);
+
+// <string_view>
+static_assert(std::input_or_output_iterator<std::string_view::iterator>);
+static_assert(std::input_or_output_iterator<std::string_view::const_iterator>);
+static_assert(std::input_or_output_iterator<std::string_view::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::string_view::const_reverse_iterator>);
+
+// <unordered_map>
+static_assert(std::input_or_output_iterator<std::unordered_map<int, int>::iterator>);
+static_assert(std::input_or_output_iterator<std::unordered_map<int, int>::const_iterator>);
+
+static_assert(std::input_or_output_iterator<std::unordered_multimap<int, int>::iterator>);
+static_assert(std::input_or_output_iterator<std::unordered_multimap<int, int>::const_iterator>);
+
+// <unordered_set>
+static_assert(std::input_or_output_iterator<std::unordered_set<int>::iterator>);
+static_assert(std::input_or_output_iterator<std::unordered_set<int>::const_iterator>);
+
+static_assert(std::input_or_output_iterator<std::unordered_multiset<int, int>::iterator>);
+static_assert(std::input_or_output_iterator<std::unordered_multiset<int, int>::const_iterator>);
+
+// <vector>
+static_assert(std::input_or_output_iterator<std::vector<int>::iterator>);
+static_assert(std::input_or_output_iterator<std::vector<int>::const_iterator>);
+static_assert(std::input_or_output_iterator<std::vector<int>::reverse_iterator>);
+static_assert(std::input_or_output_iterator<std::vector<int>::const_reverse_iterator>);
+static_assert(!std::input_or_output_iterator<std::vector<int> >);
+} // namespace standard_types

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.iterator/subsumption.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 In>
+// concept input_or_output_iterator;
+
+#include <iterator>
+
+// clang-format off
+template<std::weakly_incrementable>
+[[nodiscard]] constexpr bool check_subsumption() {
+  return false;
+}
+
+template<std::input_or_output_iterator>
+[[nodiscard]] constexpr bool check_subsumption() {
+  return true;
+}
+// clang-format on
+
+static_assert(check_subsumption<int*>());

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.sentinel/sentinel_for.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 In>
+// concept sentinel_for;
+
+#include <iterator>
+
+#include <array>
+#include <concepts>
+#include <deque>
+#ifndef _LIBCPP_HAS_NO_FILESYSTEM_LIBRARY
+#include <filesystem>
+#endif
+#include <forward_list>
+#include <list>
+#include <map>
+#include <memory>
+#include <set>
+#include <string>
+#include <string_view>
+#include <optional>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+struct nth_element_sentinel {
+  bool operator==(std::input_or_output_iterator auto) const;
+};
+static_assert(std::sentinel_for<nth_element_sentinel, std::vector<int>::iterator>);
+static_assert(std::sentinel_for<nth_element_sentinel, std::deque<int>::iterator>);
+
+struct not_semiregular {
+  not_semiregular() = delete;
+  bool operator==(std::input_or_output_iterator auto) const;
+};
+static_assert(!std::sentinel_for<not_semiregular, std::vector<int>::iterator>);
+
+struct weakly_equality_comparable_with_int {
+  bool operator==(int) const;
+};
+static_assert(!std::sentinel_for<weakly_equality_comparable_with_int, int>);
+
+struct move_only_iterator {
+  using value_type = int;
+  using difference_type = std::ptrdiff_t;
+
+  move_only_iterator() = default;
+
+  move_only_iterator(move_only_iterator&&) = default;
+  move_only_iterator& operator=(move_only_iterator&&) = default;
+
+  move_only_iterator(move_only_iterator const&) = delete;
+  move_only_iterator& operator=(move_only_iterator const&) = delete;
+
+  value_type operator*() const;
+  move_only_iterator& operator++();
+  move_only_iterator operator++(int);
+
+  bool operator==(move_only_iterator const&) const = default;
+};
+
+static_assert(!std::sentinel_for<move_only_iterator, move_only_iterator>);
+
+namespace standard_types {
+static_assert(std::sentinel_for<int*, int*>);
+
+template <class T>
+constexpr bool check_sentinel_for() {
+  using iterator = typename T::iterator;
+  using const_iterator = typename T::const_iterator;
+
+  static_assert(std::sentinel_for<iterator, iterator>);
+  static_assert(std::sentinel_for<iterator, const_iterator>);
+  static_assert(std::sentinel_for<const_iterator, iterator>);
+  static_assert(std::sentinel_for<const_iterator, const_iterator>);
+
+  return true;
+}
+
+template <class T>
+constexpr bool check_sentinel_for_with_reverse_iterators() {
+  check_sentinel_for<T>();
+
+  using iterator = typename T::iterator;
+  using const_iterator = typename T::const_iterator;
+  using reverse_iterator = typename T::reverse_iterator;
+  using const_reverse_iterator = typename T::const_reverse_iterator;
+
+  static_assert(!std::sentinel_for<iterator, reverse_iterator>);
+  static_assert(!std::sentinel_for<iterator, const_reverse_iterator>);
+  static_assert(!std::sentinel_for<const_iterator, reverse_iterator>);
+  static_assert(!std::sentinel_for<const_iterator, const_reverse_iterator>);
+
+  static_assert(!std::sentinel_for<reverse_iterator, iterator>);
+  static_assert(!std::sentinel_for<reverse_iterator, const_iterator>);
+  static_assert(std::sentinel_for<reverse_iterator, reverse_iterator>);
+  static_assert(std::sentinel_for<reverse_iterator, const_reverse_iterator>);
+
+  static_assert(!std::sentinel_for<const_reverse_iterator, iterator>);
+  static_assert(!std::sentinel_for<const_reverse_iterator, const_iterator>);
+  static_assert(std::sentinel_for<const_reverse_iterator, reverse_iterator>);
+  static_assert(std::sentinel_for<const_reverse_iterator, const_reverse_iterator>);
+
+  return true;
+}
+
+// <filesystem>
+#ifndef _LIBCPP_HAS_NO_FILESYSTEM_LIBRARY
+static_assert(std::sentinel_for<std::filesystem::directory_iterator, std::filesystem::directory_iterator>);
+static_assert(
+    std::sentinel_for<std::filesystem::recursive_directory_iterator, std::filesystem::recursive_directory_iterator>);
+#endif
+
+static_assert(
+    std::sentinel_for<std::move_iterator<std::vector<int>::iterator>, std::move_iterator<std::vector<int>::iterator> >);
+
+static_assert(check_sentinel_for_with_reverse_iterators<std::array<int, 10> >());
+static_assert(check_sentinel_for_with_reverse_iterators<std::deque<int> >());
+static_assert(check_sentinel_for<std::forward_list<int> >());
+static_assert(check_sentinel_for_with_reverse_iterators<std::list<int> >());
+static_assert(check_sentinel_for_with_reverse_iterators<std::vector<int> >());
+
+static_assert(check_sentinel_for_with_reverse_iterators<std::map<int, int> >());
+static_assert(check_sentinel_for_with_reverse_iterators<std::multimap<int, int> >());
+static_assert(check_sentinel_for_with_reverse_iterators<std::set<int> >());
+static_assert(check_sentinel_for_with_reverse_iterators<std::multiset<int> >());
+
+static_assert(check_sentinel_for_with_reverse_iterators<std::string>());
+static_assert(check_sentinel_for_with_reverse_iterators<std::string_view>());
+
+static_assert(check_sentinel_for<std::unordered_map<int, int> >());
+static_assert(check_sentinel_for<std::unordered_multimap<int, int> >());
+static_assert(check_sentinel_for<std::unordered_set<int> >());
+static_assert(check_sentinel_for<std::unordered_multiset<int> >());
+
+} // namespace standard_types

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/iterator.concept.sentinel/sentinel_for.subsumption.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 In>
+// concept sentinel_for;
+
+#include <iterator>
+
+#include <concepts>
+#include <vector>
+
+// clang-format off
+template<std::input_or_output_iterator, std::semiregular>
+[[nodiscard]] constexpr bool check_sentinel_subsumption() {
+  return false;
+}
+
+template<class I, std::sentinel_for<I> >
+[[nodiscard]] constexpr bool check_subsumption() {
+  return true;
+}
+// clang-format on
+
+static_assert(check_subsumption<std::vector<int>::iterator, std::vector<int>::iterator>());

libcxx/test/std/iterators/iterator.requirements/iterator.concepts/locale_dependent.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
+// REQUIRES: locale.en_US.UTF-8
+
+// template<class In>
+// concept input_or_output_iterator;
+
+// template<class S, class I>
+// concept sentinel_for;
+
+// template<class S, class I>
+// concept sized_sentinel_for;
+
+#include <iterator>
+
+#include <istream>
+#include <ostream>
+
+static_assert(std::input_or_output_iterator<std::istream_iterator<int, char> >);
+static_assert(std::sentinel_for<std::istream_iterator<int, char>, std::istream_iterator<int, char> >);
+
+static_assert(std::input_or_output_iterator<std::istreambuf_iterator<char> >);
+static_assert(std::sentinel_for<std::istreambuf_iterator<char>, std::istreambuf_iterator<char> >);
+
+static_assert(!std::input_or_output_iterator<std::ostream_iterator<int, char> >);
+static_assert(!std::sentinel_for<std::ostream_iterator<int, char>, std::ostream_iterator<int, char> >);
+
+static_assert(!std::input_or_output_iterator<std::ostreambuf_iterator<int, char> >);
+static_assert(!std::sentinel_for<std::ostreambuf_iterator<int, char>, std::ostreambuf_iterator<int, char> >);