[libc++][ranges] iterator.concept.sizedsentinel: sized_sentinel_for and disable_sized_sentinel_for.

[zoecarver]

Summary

Based on D100160.

[zoecarver]

• Small formatting changes.

[cjdb]

LGTM

[miscco]

LGTM

[zoecarver]

Thanks! I'll land it once the tests pass and parent patches are committed.

[• Quuxplusone]

Code looks good modulo naming; the test drags in a lot of extra dependencies it doesn't need.

libcxx/include/iterator

2600–2607

I'd prefer to see _Sp and _Ip just for consistency with line 2591.

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

42–47

Instead of std::input_or_output_iterator auto, how about int*:

struct IntSentinel {
    friend bool operator==(IntSentinel, int*);
    friend int operator-(IntSentinel, int*);
    friend int operator-(int*, IntSentinel);
};
static_assert(std::sized_sentinel_for<IntSentinel, int*>);
static_assert(!std::sized_sentinel_for<int*, IntSentinel>);  // IntSentinel is not an iterator

65–71

Please avoid reopening namespace std. Just

struct DoubleSentinel {
    friend bool operator==(DoubleSentinel, double*);
    friend int operator-(DoubleSentinel, double*);
    friend int operator-(double*, DoubleSentinel);
};
template<>
inline constexpr bool std::disable_sized_sentinel_for<DoubleSentinel, double*> = true;
    // notice the un-necessity of `namespace std {` here

static_assert(!std::sized_sentinel_for<DoubleSentinel, double*>);

155–162

I don't think this test should depend on <filesystem>. (As below, all you're testing here is that you can't subtract directory_iterators, and we knew that already.)

186–190

These initially confused me, but then I got it: it's because these iterators are merely bidirectional, not random-access, so they don't support operator-, so they're not "sized" sentinels. I would prefer to eliminate the dependency on the associative containers and write simply e.g.

#include "test_iterators.h"
static_assert(std::sized_sentinel_for<random_access_iterator<int*>, random_access_iterator<int*>>);
static_assert(!std::sized_sentinel_for<bidirectional_iterator<int*>, bidirectional_iterator<int*>>);

[cjdb]

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

186–190

Reiterating from previous reviews, which this one has inherited from: the point is to make sure these types are standard conforming. The dependencies are intentional.

[zoecarver]

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

186–190

SGTM. Will do.

[zoecarver]

• Apply Arthur's feedback.

[zoecarver]

Inline and remove check_sized_sentinel_for.

[cjdb]

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

155–162

and we knew that already

Which existing tests confirm this isn't possible?

[zoecarver]

@Quuxplusone does this look OK to you now?

[• Quuxplusone]

LGTM % comments — fix the nits and land it!

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

40–42

Please remove constexpr.
Ditto lines 74-76 and lines 82-86.

45–47

Nit: Either break the line between ; and //, or simply s/int_sized_sentinel/IntSentinel/ so that you don't need to break the line.

54

s/std::vector<int>::iterator/int*/; then you don't need to break the line.
Ditto on line 60.

57

Add: not_copyable() = default;
Otherwise, this isn't significantly different from the no_default_ctor case. (Remember, a class with any declared ctors doesn't get a defaulted default ctor, unless you explicitly default the default ctor.)

110–111

Remove this linebreak. Ditto through the end of the file.

131–132

s/std::vector<int>::iterator/int*/g so that you don't have to break the line.

[cjdb]

Please move all iterator concept conformance tests into their appropriate files (including re-adding any iterators that might have been deleted previously).

[zoecarver]

• Use new test structure.

[zoecarver]

• Unindent comment that got moved.

libcxx/include/__iterator/concepts.h

111 ↗

(On Diff #339398)

Any ideas as to why clang format wants to move this comment?

[zoecarver]

libcxx/include/__iterator/concepts.h

111 ↗

(On Diff #339402)

Any ideas as to why clang format wants to move this comment?

This diff moved the phab comment 🤦. This is the code comment I'm talking about.

[cjdb]

std::list hasn't had its conformance test updated, but otherwise I have one nit.

libcxx/test/std/containers/associative/map/iterator_concept_conformance.compile.pass.cpp

33–34 ↗

(On Diff #339402)

This should be for iterator, and is missing checks for iterator and const_iterator on the RHS. Same for other files too.

44–45 ↗

(On Diff #339402)

Missing checks for iterator and const_iterator on the RHS. Same for other files too.

libcxx/test/std/containers/sequences/array/iterator_concept_conformance.compile.pass.cpp

42–60 ↗

(On Diff #339402)

Could we order these as if they were a set of increasing two digit numbers please?
Where

iterator: 0
const_iterator: 1
reverse_iterator: 2
const_reverse_iterator: 3

I think that will make it easier to track that all have been accounted for in the right permutation.

libcxx/test/std/containers/unord/unord.map/iterator_concept_conformance.compile.pass.cpp

61 ↗

(On Diff #339402)

local_iterator and const_local_iterator need checking too please.

[zoecarver]

• Ensure line break for every changed file.

[zoecarver]

• Add, fix, and reorder tests.

[zoecarver]

I'll land as soon as the two parent patches are committed.

[cjdb]

std::list still hasn't had its conformance test updated.

libcxx/test/std/containers/sequences/deque/iterator_concept_conformance.compile.pass.cpp

53–61 ↗

(On Diff #339462)

Thos lot isn't necessary (std::reverse_iterator gets its own file so it doesn't need to be on the LHS, but it looks to me like that file is missing?).

[zoecarver]

• Remove reverse iterator tests.
• Add a test in reverse.iterator.

[zoecarver]

std::list still hasn't had its conformance test updated.

For any future reviewers: this is done.

[zoecarver]

• Rebase.
• Fix 32bit bots.

[zoecarver]

By the way, the windows bots were failing (everything else passed) because I didn't have an XFAIL on the added test but I added that before committing.

libcxx/include/iterator

 // [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
 
+// [iterator.concept.sizedsentinel], concept sized_sentinel_for
+template<class S, class I>
+  inline constexpr bool disable_sized_sentinel_for = false;
+
+template<class S, class I>
+  concept sized_sentinel_for = see below;
+
 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;

 
 // [iterator.concept.sentinel]
 template<class _Sp, class _Ip>
 concept sentinel_for =
   semiregular<_Sp> &&
   input_or_output_iterator<_Ip> &&
   __weakly_equality_comparable_with<_Sp, _Ip>;
 
+template<class, class>
+inline constexpr bool disable_sized_sentinel_for = false;
+
+template<class _Sentinel, class _Iter>
+concept sized_sentinel_for =
+  sentinel_for<_Sentinel, _Iter> &&
+  !disable_sized_sentinel_for<remove_cv_t<_Sentinel>, remove_cv_t<_Iter>> &&
+  requires(const _Iter& __i, const _Sentinel& __s) {
+    { __s - __i } -> same_as<iter_difference_t<_Iter>>;
+    { __i - __s } -> same_as<iter_difference_t<_Iter>>;
+  };
+
 #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.sentinel/sized_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
+
+// [iterator.concept.sizedsentinel], concept sized_sentinel_for
+//
+// template<class S, class I>
+//   inline constexpr bool disable_sized_sentinel_for = false;
+//
+// template<class S, class I>
+//   concept sized_sentinel_for = see below;
+
+#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 {
+  friend constexpr bool operator==(nth_element_sentinel,
+                                   std::input_or_output_iterator auto);
+  friend constexpr long operator-(nth_element_sentinel,
+                                  std::input_or_output_iterator auto);
+  friend constexpr long operator-(std::input_or_output_iterator auto,
+                                  nth_element_sentinel);
+};
+static_assert(std::sized_sentinel_for<nth_element_sentinel, int*>);
+
+struct no_default_ctor {
+  no_default_ctor() = delete;
+  bool operator==(std::input_or_output_iterator auto) const;
+};
+static_assert(
+    !std::sized_sentinel_for<no_default_ctor, std::vector<int>::iterator>);
+
+struct not_copyable {
+  not_copyable(not_copyable const&) = delete;
+  bool operator==(std::input_or_output_iterator auto) const;
+};
+static_assert(
+    !std::sized_sentinel_for<not_copyable, std::vector<int>::iterator>);
+
+namespace std {
+
+template <>
+inline constexpr bool
+    disable_sized_sentinel_for<nth_element_sentinel, double*> = true;
+
+}
+
+static_assert(std::sized_sentinel_for<nth_element_sentinel, float*>);
+static_assert(!std::sized_sentinel_for<nth_element_sentinel, double*>);
+
+struct only_one_sub_op {
+  friend constexpr bool operator==(only_one_sub_op,
+                                   std::input_or_output_iterator auto);
+  friend constexpr long operator-(only_one_sub_op,
+                                  std::input_or_output_iterator auto);
+};
+static_assert(!std::sized_sentinel_for<only_one_sub_op, int*>);
+
+struct wrong_return_type {
+  friend constexpr bool operator==(wrong_return_type,
+                                   std::input_or_output_iterator auto);
+  friend constexpr long operator-(wrong_return_type,
+                                  std::input_or_output_iterator auto);
+  friend constexpr void operator-(std::input_or_output_iterator auto,
+                                  wrong_return_type);
+};
+static_assert(!std::sized_sentinel_for<wrong_return_type, int*>);
+
+namespace standard_types {
+static_assert(std::sized_sentinel_for<int*, int*>);
+
+template <class T>
+constexpr bool check_sized_sentinel_for() {
+  using iterator = typename T::iterator;
+  using const_iterator = typename T::const_iterator;
+
+  static_assert(std::sized_sentinel_for<iterator, iterator>);
+  static_assert(std::sized_sentinel_for<iterator, const_iterator>);
+  static_assert(std::sized_sentinel_for<const_iterator, iterator>);
+  static_assert(std::sized_sentinel_for<const_iterator, const_iterator>);
+
+  return true;
+}
+
+template <class T>
+constexpr bool check_not_sized_sentinel_for() {
+  using iterator = typename T::iterator;
+  using const_iterator = typename T::const_iterator;
+
+  static_assert(!std::sized_sentinel_for<iterator, iterator>);
+  static_assert(!std::sized_sentinel_for<iterator, const_iterator>);
+  static_assert(!std::sized_sentinel_for<const_iterator, iterator>);
+  static_assert(!std::sized_sentinel_for<const_iterator, const_iterator>);
+
+  return true;
+}
+
+template <class T>
+constexpr bool check_sized_sentinel_for_with_reverse_iterators() {
+  check_sized_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::sized_sentinel_for<iterator, reverse_iterator>);
+  static_assert(!std::sized_sentinel_for<iterator, const_reverse_iterator>);
+  static_assert(!std::sized_sentinel_for<const_iterator, reverse_iterator>);
+  static_assert(
+      !std::sized_sentinel_for<const_iterator, const_reverse_iterator>);
+
+  static_assert(!std::sized_sentinel_for<reverse_iterator, iterator>);
+  static_assert(!std::sized_sentinel_for<reverse_iterator, const_iterator>);
+  static_assert(std::sized_sentinel_for<reverse_iterator, reverse_iterator>);
+  static_assert(
+      std::sized_sentinel_for<reverse_iterator, const_reverse_iterator>);
+
+  static_assert(!std::sized_sentinel_for<const_reverse_iterator, iterator>);
+  static_assert(
+      !std::sized_sentinel_for<const_reverse_iterator, const_iterator>);
+  static_assert(
+      std::sized_sentinel_for<const_reverse_iterator, reverse_iterator>);
+  static_assert(
+      std::sized_sentinel_for<const_reverse_iterator, const_reverse_iterator>);
+
+  return true;
+}
+
+// <filesystem>
+#ifndef _LIBCPP_HAS_NO_FILESYSTEM_LIBRARY
+static_assert(!std::sized_sentinel_for<std::filesystem::directory_iterator,
+                                       std::filesystem::directory_iterator>);
+static_assert(
+    !std::sized_sentinel_for<std::filesystem::recursive_directory_iterator,
+                             std::filesystem::recursive_directory_iterator>);
+#endif
+
+static_assert(
+    std::sized_sentinel_for<std::move_iterator<std::vector<int>::iterator>,
+                            std::move_iterator<std::vector<int>::iterator> >);
+
+static_assert(
+    check_sized_sentinel_for_with_reverse_iterators<std::array<int, 10> >());
+static_assert(
+    check_sized_sentinel_for_with_reverse_iterators<std::deque<int> >());
+static_assert(check_not_sized_sentinel_for<std::forward_list<int> >());
+static_assert(check_not_sized_sentinel_for<std::list<int> >());
+static_assert(
+    check_sized_sentinel_for_with_reverse_iterators<std::vector<int> >());
+
+static_assert(check_not_sized_sentinel_for<std::map<int, int> >());
+static_assert(check_not_sized_sentinel_for<std::multimap<int, int> >());
+static_assert(check_not_sized_sentinel_for<std::set<int> >());
+static_assert(check_not_sized_sentinel_for<std::multiset<int> >());
+
+static_assert(check_sized_sentinel_for_with_reverse_iterators<std::string>());
+static_assert(
+    check_sized_sentinel_for_with_reverse_iterators<std::string_view>());
+
+static_assert(check_not_sized_sentinel_for<std::unordered_map<int, int> >());
+static_assert(
+    check_not_sized_sentinel_for<std::unordered_multimap<int, int> >());
+static_assert(check_not_sized_sentinel_for<std::unordered_set<int> >());
+static_assert(check_not_sized_sentinel_for<std::unordered_multiset<int> >());
+
+} // namespace standard_types