[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

440

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

447

This should be class

449

The __has_integral_minus Is not obvious should have add a comment?

[Mordante]

libcxx/include/iterator

445

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

454

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

19 ↗

(On Diff #335166)

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

[miscco]

libcxx/include/iterator

449

Please disregard, read the other patch

[cjdb]

applies feedback from @miscco and @Mordante

libcxx/include/iterator

440

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

19 ↗

(On Diff #335166)

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

449

I can't find your comment anywhere else?

[• Quuxplusone]

libcxx/include/iterator

438–439

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 ↗

(On Diff #335172)

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

24–45

FWIW, this indentation is insane.

[cjdb]

makes iter_difference_t and iter_value_t SFINAE-friendly and consolidates test files

[cjdb]

libcxx/include/iterator

438–439

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 ↗

(On Diff #335172)

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

445

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

445

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

440

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

445

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

445

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

24–45

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/incrementable_traits.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_INCREMENTABLE_TRAITS_H
 #define _LIBCPP___ITERATOR_INCREMENTABLE_TRAITS_H
 
 #include <__config>
 #include <__iterator/concepts.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
concept __has_integral_minus =
   };
 
 template<__has_integral_minus _Tp>
 requires (!__has_member_difference_type<_Tp>)
 struct incrementable_traits<_Tp> {
   using difference_type = make_signed_t<decltype(declval<_Tp>() - declval<_Tp>())>;
 };
 
+template <class>
+struct iterator_traits;
+
+// Let `RI` be `remove_­cvref_­t<I>`. The type `iter_­difference_­t<I>` denotes
+// `incrementable_­traits<RI>::difference_­type` if `iterator_­traits<RI>` names a specialization
+// generated from the primary template, and `iterator_­traits<RI>::difference_­type` otherwise.
+template <class _Ip>
+using iter_difference_t = typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value,
+                                                 incrementable_traits<remove_cvref_t<_Ip> >,
+                                                 iterator_traits<remove_cvref_t<_Ip> > >::difference_type;
+
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ITERATOR_INCREMENTABLE_TRAITS_H

libcxx/include/__iterator/readable_traits.h

 struct indirectly_readable_traits<_Tp> {};
 template<__has_member_value_type _Tp>
 requires __has_member_element_type<_Tp> &&
          same_as<remove_cv_t<typename _Tp::element_type>,
                  remove_cv_t<typename _Tp::value_type>>
 struct indirectly_readable_traits<_Tp>
   : __cond_value_type<typename _Tp::value_type> {};
 
+template <class>
+struct iterator_traits;
+
+// Let `RI` be `remove_­cvref_­t<I>`. The type `iter_­value_­t<I>` denotes
+// `indirectly_­readable_­traits<RI>::value_­type` if `iterator_­traits<RI>` names a specialization
+// generated from the primary template, and `iterator_­traits<RI>::value_­type` otherwise.
+template <class _Ip>
+using iter_value_t = typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value,
+                                            indirectly_readable_traits<remove_cvref_t<_Ip> >,
+                                            iterator_traits<remove_cvref_t<_Ip> > >::value_type;
+
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ITERATOR_READABLE_TRAITS_H

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;
 
 template<class T>
   requires is_object_v<T>                    // since C++20
 struct iterator_traits<T*>;
 

 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template<class _Category, class _Tp, class _Distance = ptrdiff_t,
          class _Pointer = _Tp*, class _Reference = _Tp&>
 struct _LIBCPP_TEMPLATE_VIS iterator
 {
     typedef _Tp        value_type;
     typedef _Distance  difference_type;
     typedef _Pointer   pointer;
     typedef _Reference reference;
     typedef _Category  iterator_category;
 };
 
 template <class _InputIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 void __advance(_InputIter& __i,
              typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag)
 {
     for (; __n > 0; --__n)
         ++__i;
 }
 
 template <class _BiDirIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 void __advance(_BiDirIter& __i,
              typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)

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>());
+
+// clang-format off
+template <class T>
+requires requires { typename std::iter_difference_t<T>; }
+[[nodiscard]] constexpr bool check_no_iter_difference_t() {
+  return false;
+}
+// clang-format on
+
+template <class T>
+[[nodiscard]] constexpr bool check_no_iter_difference_t() {
+  return true;
+}
+
+static_assert(check_no_iter_difference_t<void>());
+static_assert(check_no_iter_difference_t<double>());
+
+struct S {};
+static_assert(check_no_iter_difference_t<S>());
+
+struct void_subtraction {
+  friend void operator-(void_subtraction, void_subtraction);
+};
+static_assert(check_no_iter_difference_t<void_subtraction>());
+
+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>());
+
+// clang-format off
+template <class T>
+requires requires { typename std::iter_value_t<T>; }
+[[nodiscard]] constexpr bool check_no_iter_value_t() {
+  return false;
+}
+// clang-format on
+
+template <class T>
+[[nodiscard]] constexpr bool check_no_iter_value_t() {
+  return true;
+}
+
+static_assert(check_no_iter_value_t<void>());
+static_assert(check_no_iter_value_t<double>());
+
+struct S {};
+static_assert(check_no_iter_value_t<S>());
+
+struct different_value_element_members {
+  using value_type = int;
+  using element_type = long;
+};
+static_assert(check_no_iter_value_t<different_value_element_members>());
+
+int main(int, char**) { return 0; }