[libcxx] adds `iter_difference_t` and `iter_value_t`

[cjdb]

Summary

Implements parts of:

• P0896R4 The One Ranges Proposal

Depends on D99855.

[miscco]

libcxx/include/iterator

490

This should be class

492

The __has_integral_minus Is not obvious should have add a comment?

551

Can we get rid of the __extract_iter_value_t struct alltogether and always fall back to an alias?

template<class _Ip>
requires __is_primary_template<iterator_traits<remove_cvref_t<_Ip>>>::value &&
         __has_member_value_type<indirectly_readable_traits<remove_cvref_t<_Ip>>>
using iter_value_t = typename indirectly_readable_traits<remove_cvref_t<_Ip>>::value_type;

template<class _Ip>
using iter_value_t = typename iterator_traits<remove_cvref_t<_Ip>>::value_type;

That way we would get around all those type instantiations, which are quite costly

[Mordante]

libcxx/include/iterator

556

For consistency, please add backticks around indirectly_­readable_­traits<R[I]>::value_­type.

565

For consistency, please add backticks around iterator_­traits<R[I]>::value_­type.

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/incrementable.traits/iter_difference_t.fail.cpp

20

Why not use a specific offset like expected-errror@-1?

[miscco]

libcxx/include/iterator

492

Please disregard, read the other patch

[cjdb]

applies feedback from @miscco and @Mordante

libcxx/include/iterator

551

Aliases can't be specialised. Might be worth a compiler patch to elide this if it's deemed too costly?

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/incrementable.traits/iter_difference_t.fail.cpp

20

The error originates from <iterator>, not this file (I originally did expected-error@-1 which is how I learnt about @iterator:* when it failed).

[cjdb]

libcxx/include/iterator

492

I can't find your comment anywhere else?

[• Quuxplusone]

libcxx/include/iterator

549–569

Slightly disentangled: so that code doesn't interrupt the flow of an English sentence, and the primary template isn't forward-declared.

I think this is fine; but it does feel weird at a higher level that http://eel.is/c++draft/sequences#general-2 already defines __iter_value_type (as an exposition-only implementation detail related to container deduction guides), and here http://eel.is/c++draft/readable.traits#2 is introducing iter_value_t with a subtly different meaning. libc++ maintainers will have to be careful to pick the right one.

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/incrementable.traits/iter_difference_t.fail.cpp

32

FWIW, I think it would make more sense to cast all these tests in terms of what we do expect to be true, instead of relying on compiler error messages.
For example, if we expect that the type std::iter_difference_t<void_subtraction> doesn't exist, we could maybe do

template<class T> auto has_no_difference_type(int) -> std::void_t<std::iter_difference_t<T>> {}
template<class T> bool has_no_difference_type(long) { return true; }

int main(int, char**)
{
    assert(has_no_difference_type<void_subtraction>(42));

    return 0;
}

But this is assuming that iter_difference_t<T> is supposed to be SFINAE-friendly. I don't know if that's actually guaranteed/intended by the Standard.

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/incrementable.traits/iter_difference_t.pass.cpp

23–44

FWIW, this indentation is insane.

[cjdb]

makes iter_difference_t and iter_value_t SFINAE-friendly and consolidates test files

[cjdb]

libcxx/include/iterator

549–569

The mixing of standardese with code was intentional, to show which bits of code correspond to which bits of the standard. This idea was taken from <type_traits>.

In future, for something as trivial as this, please request what you're after instead of providing a full-blown suggested edit.

I think this is fine; but it does feel weird at a higher level that http://eel.is/c++draft/sequences#general-2 already defines __iter_value_type (as an exposition-only implementation detail related to container deduction guides), and here http://eel.is/c++draft/readable.traits#2 is introducing iter_value_t with a subtly different meaning. libc++ maintainers will have to be careful to pick the right one.

I think the best thing to do would be to ask LWG to consider renaming iter-value-type to something else (it might even be possible to do this editorially after a mailing discussion), or us just doing so regardless of what LWG thinks, so as to avoid confusion.

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/incrementable.traits/iter_difference_t.fail.cpp

32

The wording is SFINAE-friendly, but my implementation here wasn't due to a mistake in translating from cjdb-ranges to libc++.

[cjdb]

rebases to activate CI

[• Quuxplusone]

libcxx/include/iterator

488

Please write RI, not R[I]. (I know you're trying to reflect that the I in the standard is a subscript letter. However, it's not an array index, and RI functions semantically as a single identifier — there is no separate entity R to be discussed, so we don't need a name for it.)

I don't think you should be instantiating incrementable_traits<RI> in the case that iterator_traits<RI> is the primary template. Please (1) check what the Standard's intent here is, (2) make the fix if needed, and (3) add a test case that detects the fix.

Separately and presumably a moot point in this case: note that conditional_t is compile-time-wasting by design. Anywhere in libc++ that we need its effects and aren't mandated to use conditional_t, we should be using Eric's _If<is-blah, incr-traits, iter-traits> because it instantiates fewer templates.

[cjdb]

replaces conditional_t with _If

[cjdb]

libcxx/include/iterator

488

I don't think you should be instantiating incrementable_traits<RI> in the case that iterator_traits<RI> is the primary template. Please (1) check what the Standard's intent here is, (2) make the fix if needed, and (3) add a test case that detects the fix.

It's pretty much left up to us. MSVC's implementation is identical to the conditional_t one, for example, and @CaseyCarter understands the intention better than us all.

[tcanens]

libcxx/include/iterator

483

This now has a mix of RI and R[I]

488

I don't think you should be instantiating incrementable_traits<RI> in the case that iterator_traits<RI> is the primary template.

What does this even mean? How do you produce incrementable_­traits<RI>::difference_­type without instantiating incrementable_­traits<RI>?

[• Quuxplusone]

libcxx/include/iterator

488

I flipped the logic by accident. I should have said, don't instantiate incrementable_traits<RI> in the case that iterator_traits<RI> is not the primary template, i.e. in the case when we want to just go ahead and trust iterator_traits<RI>::value_type. (And I almost made the exact same error again in typing up this message! Note to self: Here "primary" means "the one we don't want to use.")

[cjdb]

rebases to activate CI

[cjdb]

reverts _If to conditional_t to avoid substitution failure problem in future commits

[• Quuxplusone]

@cjdb wrote:

reverts _If to conditional_t to avoid substitution failure problem in future commits

Is this because of Clang bug https://bugs.llvm.org/show_bug.cgi?id=44833#c5 ? If so, that Clang bug is probably going to block a lot of Ranges implementation until it's fixed, anyway. @ldionne, do you have any guidance here? (1) Should libc++ aim to be the one standard library that works around this Clang bug, or should we just pressure Clang to fix their bug? (2) In the short term, assuming the bug won't be fixed tomorrow, how much should Chris work around Clang bugs in these patches versus just delaying the patches until Clang is ready?

[ldionne]

In D99863#2685482, @Quuxplusone wrote:

@cjdb wrote:

reverts _If to conditional_t to avoid substitution failure problem in future commits

Is this because of Clang bug https://bugs.llvm.org/show_bug.cgi?id=44833#c5 ? If so, that Clang bug is probably going to block a lot of Ranges implementation until it's fixed, anyway. @ldionne, do you have any guidance here? (1) Should libc++ aim to be the one standard library that works around this Clang bug, or should we just pressure Clang to fix their bug? (2) In the short term, assuming the bug won't be fixed tomorrow, how much should Chris work around Clang bugs in these patches versus just delaying the patches until Clang is ready?

I think we need to push hard on Clang to fix this bug. If working around it for now is feasible then let's do that, but I would not go too far in that direction.

[cjdb]

rebases to activate CI

[ldionne]

I think this LGTM. There's some small comments about a missed R[I] -> RI transformation, but I think that's all. LGTM with nitpicks applied.

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/incrementable.traits/iter_difference_t.pass.cpp

23–44

Can we please keep comments constructive and polite? It's fine to disagree with the way of formatting things. It's also fine to request changes on a patch due to indentation or some other format-related issue that impacts readability. But please try to root your comment in something objective.

[cjdb]

s/R[I]/RI/

[cjdb]

rebases to activate CI

[cjdb]

Merged ahead of CI reaching 100% with permission from @ldionne. Apparently only the santatizers, macos, gcc, c++03, and C++20 builds are the most important.

libcxx/include/iterator

 /*
     iterator synopsis
 
 #include <concepts>
 
 namespace std
 {
 template<class> struct incrementable_traits;       // since C++20
+template<class T>
+  using iter_difference_t = see below;             // since C++20
+
 template<class> struct indirectly_readable_traits; // since C++20
+template<class T>
+  using iter_value_t = see below;                  // since C++20
 
 template<class Iterator>
 struct iterator_traits
 {
     typedef typename Iterator::difference_type difference_type;
     typedef typename Iterator::value_type value_type;
     typedef typename Iterator::pointer pointer;
     typedef typename Iterator::reference reference;

 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Iter>
+struct _LIBCPP_TEMPLATE_VIS iterator_traits;
+
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
 // [incrementable.traits]
 template<class> struct incrementable_traits {};
 
 template<class _Tp>
 requires is_object_v<_Tp>
 struct incrementable_traits<_Tp*> {
   using difference_type = ptrdiff_t;
requires(const _Tp& __x, const _Tp& __y) {
     { __x - __y } -> integral;
   };
 
 template<__has_integral_minus _Tp>
 struct incrementable_traits<_Tp> {
   using difference_type = make_signed_t<decltype(declval<_Tp>() - declval<_Tp>())>;
 };
 
-// TODO(cjdb): add iter_difference_t once iterator_traits is cleaned up.
+// Let `R[I]` be `remove_­cvref_­t<I>`. The type `iter_­difference_­t<I>` denotes
+template<class>
+struct __extract_iter_difference_t;
+
+template<class _Ip>
+using iter_difference_t = typename __extract_iter_difference_t<remove_cvref_t<_Ip>>::type;
+
+// `incrementable_­traits<R[I]>::difference_­type` if `iterator_­traits<R[I]>` names a specialization
+// generated from the primary template, and
+template<class _Ip>
+requires __is_primary_template<iterator_traits<_Ip>>::value &&
+         (__has_member_difference_type<_Ip> || __has_integral_minus<_Ip>)
+struct __extract_iter_difference_t<_Ip> {
+  using type = typename incrementable_traits<_Ip>::difference_type;
+};
+
+// `iterator_­traits<R[I]>::difference_­type` otherwise.
+template<class _Ip>
+struct __extract_iter_difference_t {
+  using type = typename iterator_traits<_Ip>::difference_type;
+};
 
 // [readable.traits]
 template<class> struct indirectly_readable_traits {};
 
 template<class _Ip>
 requires is_array_v<_Ip>
 struct indirectly_readable_traits<_Ip> {
   using value_type = remove_cv_t<remove_extent_t<_Ip>>;
concept __has_members_value_type_and_element_type =
   __has_member_element_type<_Tp> &&
   same_as<remove_cv_t<typename _Tp::element_type>,
           remove_cv_t<typename _Tp::value_type>>;
 
 template<__has_members_value_type_and_element_type _Tp>
 struct indirectly_readable_traits<_Tp>
   : __cond_value_type<typename _Tp::value_type> {};
 
-// TODO(cjdb): add iter_value_t once iterator_traits is cleaned up.
+// Let `R[I]` be `remove_­cvref_­t<I>`. The type `iter_­value_­t<I>` denotes
+template<class>
+struct __extract_iter_value_t;
+
+template<class _Ip>
+using iter_value_t = typename __extract_iter_value_t<remove_cvref_t<_Ip>>::type;
+
+// `indirectly_­readable_­traits<R[I]>::value_­type` if `iterator_­traits<R[I]>` names a specialization
+// generated from the primary template, and
+template<class _Ip>
+requires __is_primary_template<iterator_traits<_Ip>>::value &&
+         __has_member_value_type<indirectly_readable_traits<_Ip>>
+struct __extract_iter_value_t<_Ip> {
+  using type = typename indirectly_readable_traits<_Ip>::value_type;
+};
+
+// `iterator_­traits<R[I]>::value_­type` otherwise.
+template<class _Ip>
+struct __extract_iter_value_t {
+  using type = typename iterator_traits<_Ip>::value_type;
+};
 
 template<class _Tp>
 using __with_reference = _Tp&;
 
 template<class _Tp>
 concept __can_reference = requires {
   typename __with_reference<_Tp>;
 };
 
 template<class _Tp>
 concept __dereferenceable = requires(_Tp& __t) {
   { *__t } -> __can_reference; // not required to be equality-preserving
 };
 
 template<__dereferenceable _Tp>
 using iter_reference_t = decltype(*declval<_Tp&>());
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
 
-template <class _Iter>
-struct _LIBCPP_TEMPLATE_VIS iterator_traits;
-
 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag       : public input_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
 #if _LIBCPP_STD_VER > 17
 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag    : public random_access_iterator_tag {};
 #endif

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/incrementable.traits/iter_difference_t.fail.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 T>
+// using iter_difference_t;
+
+#include <iterator>
+
+using fails1 = std::iter_difference_t<void>;
+// expected-error@iterator:* {{no type named 'difference_type' in 'std::iterator_traits<void>'}}
+
+using fails2 = std::iter_difference_t<double>;
+// expected-error@iterator:* {{no type named 'difference_type' in 'std::iterator_traits<double>'}}
+
+struct S {};
+using fails3 = std::iter_difference_t<S>;
+// expected-error@iterator:* {{no type named 'difference_type' in 'std::iterator_traits<S>'}}
+
+struct void_subtraction {
+  friend void operator-(void_subtraction, void_subtraction);
+};
+using fails4 = std::iter_difference_t<void_subtraction>;
+// expected-error@iterator:* {{no type named 'difference_type' in 'std::iterator_traits<void_subtraction>'}}
+
+int main(int, char**) { return 0; }

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/incrementable.traits/iter_difference_t.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 T>
+// using iter_difference_t;
+
+#include <iterator>
+
+#include <concepts>
+#include <vector>
+
+template <class T, class Expected>
+[[nodiscard]] constexpr bool check_iter_difference_t() {
+  constexpr bool result = std::same_as<std::iter_difference_t<T>, Expected>;
+  static_assert(std::same_as<std::iter_difference_t<T const>, Expected> ==
+                result);
+  static_assert(std::same_as<std::iter_difference_t<T volatile>, Expected> ==
+                result);
+  static_assert(
+      std::same_as<std::iter_difference_t<T const volatile>, Expected> ==
+      result);
+  static_assert(std::same_as<std::iter_difference_t<T const&>, Expected> ==
+                result);
+  static_assert(std::same_as<std::iter_difference_t<T volatile&>, Expected> ==
+                result);
+  static_assert(
+      std::same_as<std::iter_difference_t<T const volatile&>, Expected> ==
+      result);
+  static_assert(std::same_as<std::iter_difference_t<T const&&>, Expected> ==
+                result);
+  static_assert(std::same_as<std::iter_difference_t<T volatile&&>, Expected> ==
+                result);
+  static_assert(
+      std::same_as<std::iter_difference_t<T const volatile&&>, Expected> ==
+      result);
+
+  return result;
+}
+
+static_assert(check_iter_difference_t<int, int>());
+static_assert(check_iter_difference_t<int*, std::ptrdiff_t>());
+static_assert(
+    check_iter_difference_t<std::vector<int>::iterator,
+                            std::vector<int>::iterator::difference_type>());
+
+struct int_subtraction {
+  friend int operator-(int_subtraction, int_subtraction) noexcept;
+};
+static_assert(check_iter_difference_t<int_subtraction, int>());
+
+int main(int, char**) { return 0; }

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/readable.traits/iter_value_t.fail.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 T>
+// using iter_value_t;
+
+#include <iterator>
+
+using fail1 = std::iter_value_t<void>;
+// expected-error@iterator:* {{no type named 'value_type' in 'std::iterator_traits<void>'}}
+
+using fail2 = std::iter_value_t<int>;
+// expected-error@iterator:* {{no type named 'value_type' in 'std::iterator_traits<int>'}}
+
+struct S {};
+using fail3 = std::iter_value_t<S>;
+// expected-error@iterator:* {{no type named 'value_type' in 'std::iterator_traits<S>'}}
+
+struct different_value_element {
+  using value_type = int;
+  using element_type = long;
+};
+using fail4 = std::iter_value_t<different_value_element>;
+// expected-error@iterator:* {{no type named 'value_type' in 'std::iterator_traits<different_value_element>'}}
+
+int main(int, char**) { return 0; }

libcxx/test/std/iterators/iterator.requirements/iterator.assoc.types/readable.traits/iter_value_t.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 T>
+// using iter_value_t;
+
+#include <iterator>
+
+#include <concepts>
+#include <memory>
+#include <vector>
+
+template <class T, class Expected>
+[[nodiscard]] constexpr bool check_iter_value_t() {
+  constexpr bool result = std::same_as<std::iter_value_t<T>, Expected>;
+  static_assert(std::same_as<std::iter_value_t<T const>, Expected> == result);
+  static_assert(std::same_as<std::iter_value_t<T volatile>, Expected> ==
+                result);
+  static_assert(std::same_as<std::iter_value_t<T const volatile>, Expected> ==
+                result);
+  static_assert(std::same_as<std::iter_value_t<T const&>, Expected> == result);
+  static_assert(std::same_as<std::iter_value_t<T volatile&>, Expected> ==
+                result);
+  static_assert(std::same_as<std::iter_value_t<T const volatile&>, Expected> ==
+                result);
+  static_assert(std::same_as<std::iter_value_t<T const&&>, Expected> == result);
+  static_assert(std::same_as<std::iter_value_t<T volatile&&>, Expected> ==
+                result);
+  static_assert(std::same_as<std::iter_value_t<T const volatile&&>, Expected> ==
+                result);
+
+  return result;
+}
+
+static_assert(check_iter_value_t<int*, int>());
+static_assert(check_iter_value_t<int[], int>());
+static_assert(check_iter_value_t<int[10], int>());
+static_assert(check_iter_value_t<std::vector<int>::iterator,
+                                 std::vector<int>::iterator::value_type>());
+static_assert(check_iter_value_t<std::shared_ptr<int>,
+                                 std::shared_ptr<int>::element_type>());
+
+struct both_members {
+  using value_type = double;
+  using element_type = double;
+};
+static_assert(check_iter_value_t<both_members, double>());
+
+int main(int, char**) { return 0; }