diff --git a/libcxx/include/iterator b/libcxx/include/iterator --- a/libcxx/include/iterator +++ b/libcxx/include/iterator @@ -31,6 +31,7 @@ }; template + requires is_object_v // since C++20 struct iterator_traits { typedef ptrdiff_t difference_type; @@ -708,8 +709,176 @@ { __i - __j } -> same_as; { __i[__n] } -> convertible_to>; }; -#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS) +template struct __iterator_traits_member_pointer; +template struct __iterator_traits_member_reference; +template struct __iterator_traits_iterator_category; + +template +concept __has_member_reference = requires { typename _Ip::reference; }; + +template +concept __has_member_iterator_category = requires { typename _Ip::iterator_category; }; + +template +concept __specifies_members = + __has_member_reference<_Ip> && + __has_member_iterator_category<_Ip> && + requires { + typename _Ip::difference_type; + typename _Ip::value_type; + }; + +// [iterator.traits]/3.1 +// If `I` has valid ([temp.deduct]) member types `difference_­type`, `value_­type`, `reference`, and +// `iterator_­category`, then `iterator_­traits` has the following publicly accessible members: +template<__specifies_members _Ip> +struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Ip> { + using iterator_category = typename _Ip::iterator_category; + using value_type = typename _Ip::value_type; + using difference_type = typename _Ip::difference_type; + using pointer = typename __iterator_traits_member_pointer<_Ip>::type; + using reference = typename _Ip::reference; + using __primary_template = iterator_traits; +}; + +template +concept __legacy_iterator_missing_members = + !__specifies_members<_Tp> && + __legacy_iterator<_Tp>; + +template +concept __legacy_input_iterator_missing_members = + __legacy_iterator_missing_members<_Tp> && + __legacy_input_iterator<_Tp>; + +// [iterator.traits]/3.2 +// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`, +// `iterator_­traits` has the following publicly accessible members: +template<__legacy_input_iterator_missing_members _Ip> +struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Ip> { + using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type; + using value_type = typename indirectly_readable_traits<_Ip>::value_type; + using difference_type = typename incrementable_traits<_Ip>::difference_type; + using pointer = typename __iterator_traits_member_pointer<_Ip>::type; + using reference = typename __iterator_traits_member_reference<_Ip>::type; + using __primary_template = iterator_traits; +}; + +// [iterator.traits]/3.2.1 +// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type. +template +concept __has_member_pointer = requires { typename _Ip::pointer; }; + +template<__has_member_pointer _Ip> +struct __iterator_traits_member_pointer<_Ip> { using type = typename _Ip::pointer; }; + +// Otherwise, if `decltype(declval().operator->())` is well-formed, then `pointer` names that +// type. +template +concept __has_arrow = + __legacy_input_iterator_missing_members<_Ip> && + !__has_member_pointer<_Ip> && + requires(_Ip& __i) { + __i.operator->(); + }; + +template<__has_arrow _Ip> +struct __iterator_traits_member_pointer<_Ip> { + using type = decltype(declval<_Ip&>().operator->()); +}; + +// Otherwise, `pointer` names `void`. +template +struct __iterator_traits_member_pointer { using type = void; }; + +// [iterator.traits]/3.2.2 +// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type. +template<__has_member_reference _Ip> +struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; }; + +// Otherwise, `reference` names `iter_­reference_­t`. +template +struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; }; + +// [iterator.traits]/3.2.3 +// If the qualified-id `I::iterator_­category` is valid and denotes a type, `iterator_­category` names +// that type. +template<__has_member_iterator_category _Ip> +struct __iterator_traits_iterator_category<_Ip> { + using type = typename _Ip::iterator_category; +}; + +// Otherwise, iterator_­category names: +template +struct __deduce_iterator_category; + +template +struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {}; + +// [iterator.traits]/3.2.3.1 +// `random_­access_­iterator_­tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise +template<__legacy_random_access_iterator _Ip> +struct __deduce_iterator_category<_Ip> { + using type = random_access_iterator_tag; +}; + +// [iterator.traits]/3.2.3.2 +// `bidirectional_­iterator_­tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise +template<__legacy_bidirectional_iterator _Ip> +struct __deduce_iterator_category<_Ip> { + using type = bidirectional_iterator_tag; +}; + +// [iterator.traits]/3.2.3.3 +// `forward_­iterator_­tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise +template<__legacy_forward_iterator _Ip> +struct __deduce_iterator_category<_Ip> { + using type = forward_iterator_tag; +}; + +// [iterator.traits]/3.2.3.4 +// input_­iterator_­tag +template +struct __deduce_iterator_category { + using type = input_iterator_tag; +}; + + +// [iterator.traits]/3.3 +template struct __iterator_traits_difference_type; + +// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then +// `iterator_­traits` has the following publicly accessible members: +template<__legacy_iterator_missing_members _Ip> +struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Ip> { + using iterator_category = output_iterator_tag; + using value_type = void; + using difference_type = typename __iterator_traits_difference_type<_Ip>::type; + using pointer = void; + using reference = void; + using __primary_template = iterator_traits; +}; + +// If the qualified-id `incrementable_­traits::difference_­type` is valid and denotes a type, then +// `difference_­type` names that type; +template +requires requires { typename incrementable_traits<_Ip>::difference_type; } +struct __iterator_traits_difference_type<_Ip> { + using type = typename incrementable_traits<_Ip>::difference_type; +}; + +// otherwise, it names void. +template +struct __iterator_traits_difference_type { using type = void; }; + +// [iterator.traits]/3.4 +// Otherwise, `iterator_­traits` has no members by any of the above names. +template +struct _LIBCPP_TEMPLATE_VIS iterator_traits { + using __primary_template = iterator_traits; +}; +#else template struct __iterator_traits {}; template @@ -733,8 +902,12 @@ using __primary_template = iterator_traits; }; +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS) template +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS) +requires is_object_v<_Tp> +#endif struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> { typedef ptrdiff_t difference_type; diff --git a/libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.pass.cpp @@ -0,0 +1,293 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// struct iterator_traits; + +#include + +#include +#include + +#include "legacy_iterator_wrappers.h" + +template +struct explicit_members { + using iterator_category = Category; + using value_type = Value; + using difference_type = Difference; + using reference = Reference; +}; + +template +struct explicit_members_with_pointer + : explicit_members { + using pointer = typename explicit_members::value_type*; +}; + +template +[[nodiscard]] constexpr bool check_members_explicitly_provided() { + { + using fake_iterator = + explicit_members; + using iterator_traits = std::iterator_traits; + static_assert( + std::same_as); + static_assert(std::same_as); + static_assert( + std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + } + + { + using fake_iterator = + explicit_members_with_pointer; + using iterator_traits = std::iterator_traits; + static_assert( + std::same_as); + static_assert(std::same_as); + static_assert( + std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + } + return true; +} + +static_assert(check_members_explicitly_provided()); +static_assert(check_members_explicitly_provided()); +static_assert(check_members_explicitly_provided()); + +struct S {}; +static_assert(check_members_explicitly_provided()); +static_assert(check_members_explicitly_provided()); + +template +struct get_reference { + using type = std::iter_reference_t; +}; + +template > Wrapper> +struct get_reference { + using type = typename Wrapper::reference; +}; + +template +struct get_pointer { + using type = void; +}; + +template > Wrapper> +struct get_pointer { + using type = typename Wrapper::pointer; +}; + +template +struct get_pointer { + using type = decltype(std::declval().operator->()); +}; + +template +[[nodiscard]] constexpr bool check_wrapper_traits() { + using Traits = std::iterator_traits; + static_assert(std::same_as); + static_assert( + std::same_as::value_type>); + static_assert( + std::same_as::difference_type>); + static_assert(std::same_as::type>); + static_assert(std::same_as::type>); + return true; +} + +template class... Args> +requires(sizeof...(Args) > 0) constexpr + void check_with_legacy_input_iterator() { + { + using iterator = legacy_input_iterator; + static_assert(check_wrapper_traits()); + } + { + using iterator = legacy_forward_iterator; + static_assert( + check_wrapper_traits()); + } + { + using iterator = + legacy_bidirectional_iterator; + static_assert( + check_wrapper_traits()); + } + { + using iterator = + legacy_random_access_iterator; + static_assert( + check_wrapper_traits()); + } +} + +template +[[nodiscard]] constexpr bool check_with_legacy_input_iterator() { + check_with_legacy_input_iterator(); + check_with_legacy_input_iterator(); + check_with_legacy_input_iterator(); + check_with_legacy_input_iterator(); + check_with_legacy_input_iterator(); + check_with_legacy_input_iterator(); + return true; +} +static_assert(check_with_legacy_input_iterator::iterator>()); +static_assert( + check_with_legacy_input_iterator::const_iterator>()); + +template +[[nodiscard]] constexpr bool check_with_legacy_iterator() { + { + using iterator = legacy_iterator; + using iterator_traits = std::iterator_traits; + static_assert(std::same_as); + static_assert(std::same_as); + static_assert( + std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + } + { + using iterator = legacy_iterator; + using iterator_traits = std::iterator_traits; + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + static_assert(std::same_as); + } + return true; +} + +static_assert(check_with_legacy_iterator::iterator>()); +static_assert(check_with_legacy_iterator::const_iterator>()); + +template +[[nodiscard]] constexpr bool check_fails() { + static_assert( + !requires { typename std::iterator_traits::iterator_concept; }); + static_assert( + !requires { typename std::iterator_traits::iterator_category; }); + static_assert(!requires { typename std::iterator_traits::value_type; }); + static_assert( + !requires { typename std::iterator_traits::difference_type; }); + static_assert(!requires { typename std::iterator_traits::pointer; }); + static_assert(!requires { typename std::iterator_traits::reference; }); + return true; +} + +static_assert(check_fails()); +static_assert(check_fails()); +static_assert(check_fails()); +static_assert(check_fails()); +static_assert(check_fails()); + +static_assert(check_fails()); +static_assert(check_fails()); +static_assert(check_fails()); +static_assert(check_fails()); +static_assert(check_fails()); +static_assert(check_fails()); +static_assert(check_fails()); + +struct missing_iterator_category { + using value_type = int; + using difference_type = int; + using pointer = int*; + using reference = int&; +}; +static_assert(check_fails()); + +struct iterator_category_as_static_member { + using value_type = int; + using difference_type = int; + using pointer = int*; + using reference = int&; + + inline static constexpr int iterator_category = 0; +}; +static_assert(check_fails()); + +struct missing_value_type { + using iterator_category = std::input_iterator_tag; + using difference_type = int; + using pointer = int*; + using reference = int&; +}; +static_assert(check_fails()); + +struct value_type_as_static_member { + using iterator_category = std::input_iterator_tag; + using difference_type = int; + using pointer = int*; + using reference = int&; + + inline static constexpr int value_type = 0; +}; +static_assert(check_fails()); + +struct missing_difference_type { + using iterator_category = std::input_iterator_tag; + using value_type = int; + using pointer = int*; + using reference = int&; +}; +static_assert(check_fails()); + +struct difference_type_as_static_member { + using iterator_category = std::input_iterator_tag; + using value_type = int; + using pointer = int*; + using reference = int&; + + inline static constexpr int difference_type = 0; +}; +static_assert(check_fails()); + +struct missing_reference { + using iterator_category = std::input_iterator_tag; + using value_type = int; + using difference_type = int; + using pointer = int*; +}; +static_assert(check_fails()); + +struct reference_as_static_member { + using iterator_category = std::input_iterator_tag; + using value_type = int; + using difference_type = int; + using pointer = int*; + + inline static constexpr int reference = 0; +}; +static_assert(check_fails()); + +int main(int, char**) { return 0; } diff --git a/libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp --- a/libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp +++ b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp @@ -91,7 +91,7 @@ typedef T::reference RT; // expected-error-re {{no type named 'reference' in 'std:{{.*}}:iterator_traits<{{.+}}>}} typedef T::iterator_category CT; // expected-error-re {{no type named 'iterator_category' in 'std:{{.*}}:iterator_traits<{{.+}}>}} } - +#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_HAS_NO_CONCEPTS) { typedef std::iterator_traits T; typedef T::difference_type DT; // expected-error-re {{no type named 'difference_type' in 'std:{{.*}}:iterator_traits<{{.+}}>}} @@ -100,7 +100,7 @@ typedef T::reference RT; // expected-error-re {{no type named 'reference' in 'std:{{.*}}:iterator_traits<{{.+}}>}} typedef T::iterator_category CT; // expected-error-re {{no type named 'iterator_category' in 'std:{{.*}}:iterator_traits<{{.+}}>}} } - +#endif { typedef std::iterator_traits T; typedef T::difference_type DT; // expected-error-re {{no type named 'difference_type' in 'std:{{.*}}:iterator_traits<{{.+}}>}} diff --git a/libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.pass.cpp --- a/libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.pass.cpp +++ b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.pass.cpp @@ -36,6 +36,9 @@ { typedef std::iterator_traits It; static_assert(!(has_value_type::value), ""); +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS) + static_assert(!(has_value_type >::value)); +#endif - return 0; + return 0; } diff --git a/libcxx/test/std/iterators/iterator.primitives/iterator.traits/legacy_iterator_wrappers.h b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/legacy_iterator_wrappers.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/legacy_iterator_wrappers.h @@ -0,0 +1,142 @@ +//===----------------------------------------------------------------------===// +// +// 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 STD_ITERATORS_ITERATOR_PRIMITIVES_ITERATOR_TRAITS_LEGACY_ITERATORS_H +#define STD_ITERATORS_ITERATOR_PRIMITIVES_ITERATOR_TRAITS_LEGACY_ITERATORS_H + +template +concept has_arrow = requires(I& i) { + i.operator->(); +}; + +// Extension point for `legacy_iterator_wrapper` to support `operator->`. +template +struct arrow_extension : I { + using I::operator->; +}; + +// Wrapper around a legacy C++ iterator to give it a minimal interface. +// +// The key difference between these `legacy.*_iterator` types and those found in +// `support/test_iterators.h` is that the legacy iterator class are designed to support mixins and +// specifically test C++20's changes to `iterator_traits`. Namely, the absence of members and the +// arrow operator is important. +template class... Args> +class legacy_iterator : public Args... { +public: + legacy_iterator() = default; + explicit legacy_iterator(I i) : base_(i) {} + + decltype(auto) operator*() const { return *base_; } + + legacy_iterator& operator++(); + legacy_iterator operator++(int); + +private: + I base_ = I(); +}; + +// Wrapper around a legacy C++ input iterator to give it a minimal interface. +template class... Args> +class legacy_input_iterator : public legacy_iterator { +public: + using iterator_category = std::input_iterator_tag; + using legacy_iterator::legacy_iterator; + + static_assert((requires { typename Args::value_type; } || ...)); + static_assert((requires { typename Args::difference_type; } || ...)); + + bool operator==(legacy_input_iterator const&) const; + legacy_input_iterator& operator++(); + legacy_input_iterator operator++(int); +}; + +// Wrapper around a legacy C++ forward iterator to give it a minimal interface. +template class... Args> +class legacy_forward_iterator : public legacy_input_iterator { +public: + using iterator_category = std::forward_iterator_tag; + using legacy_input_iterator::legacy_input_iterator; + + legacy_forward_iterator& operator++(); + legacy_forward_iterator operator++(int); +}; + +// Wrapper around a legacy C++ bidirectional iterator to give it a minimal interface. +template class... Args> +class legacy_bidirectional_iterator + : public legacy_forward_iterator { +public: + using iterator_category = std::bidirectional_iterator_tag; + using legacy_forward_iterator::legacy_forward_iterator; + + legacy_bidirectional_iterator& operator++(); + legacy_bidirectional_iterator operator++(int); + legacy_bidirectional_iterator& operator--(); + legacy_bidirectional_iterator operator--(int); +}; + +// Wrapper around a legacy C++ random-access iterator to give it a minimal interface. +template class... Args> +class legacy_random_access_iterator + : public legacy_bidirectional_iterator { +public: + using iterator_category = std::random_access_iterator_tag; + using legacy_bidirectional_iterator::legacy_bidirectional_iterator; + using typename legacy_bidirectional_iterator::difference_type; + + legacy_random_access_iterator& operator++(); + legacy_random_access_iterator operator++(int); + legacy_random_access_iterator& operator--(); + legacy_random_access_iterator operator--(int); + legacy_random_access_iterator& operator+=(difference_type); + legacy_random_access_iterator& operator-=(difference_type); + + friend legacy_random_access_iterator operator+(legacy_random_access_iterator, + difference_type); + friend legacy_random_access_iterator operator+(difference_type, + legacy_random_access_iterator); + friend legacy_random_access_iterator operator-(legacy_random_access_iterator, + difference_type); + + difference_type operator-(legacy_random_access_iterator) const; + decltype(auto) operator[](difference_type const n) const { + return *(*this + n); + } + bool operator<(legacy_random_access_iterator) const; + bool operator>(legacy_random_access_iterator) const; + bool operator<=(legacy_random_access_iterator) const; + bool operator>=(legacy_random_access_iterator) const; +}; + +// Minimum extension point for `legacy_input_iterator`. +template +struct minimal_extension { + using difference_type = + typename std::incrementable_traits::difference_type; + using value_type = typename std::indirectly_readable_traits::value_type; +}; + +// Extension point for reference member. +template +struct reference_extension { + using reference = typename I::reference; +}; + +// Extension point for pointer member. +template +struct pointer_extension { + using pointer = typename I::pointer; +}; + +// Extension point to indicate no extension points. +// This is used for function overloading when there isn't a better name for two overloads. +template +struct empty_extension {}; + +#endif // STD_ITERATORS_ITERATOR_PRIMITIVES_ITERATOR_TRAITS_LEGACY_ITERATORS_H