diff --git a/libcxx/include/iterator b/libcxx/include/iterator --- a/libcxx/include/iterator +++ b/libcxx/include/iterator @@ -21,24 +21,11 @@ template struct indirectly_readable_traits; // since C++20 template -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; - typedef typename Iterator::iterator_category iterator_category; -}; +struct iterator_traits; template -struct iterator_traits -{ - typedef ptrdiff_t difference_type; - typedef T value_type; - typedef T* pointer; - typedef T& reference; - typedef random_access_iterator_tag iterator_category; -}; + requires is_object_v // since C++20 +struct iterator_traits; template using iter_reference_t = decltype(*declval()); @@ -637,18 +624,6 @@ static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; }; -template struct __iterator_traits_impl {}; - -template -struct __iterator_traits_impl<_Iter, true> -{ - typedef typename _Iter::difference_type difference_type; - typedef typename _Iter::value_type value_type; - typedef typename _Iter::pointer pointer; - typedef typename _Iter::reference reference; - typedef typename _Iter::iterator_category iterator_category; -}; - #if !defined(_LIBCPP_HAS_NO_RANGES) // The `cpp17.*-iterator` concepts have been dubbed `__legacy.*_iterator` because the name is both @@ -712,10 +687,191 @@ { __i - __i } -> same_as; { __i[__n] } -> convertible_to>; }; -#endif // !defined(_LIBCPP_HAS_NO_RANGES) +template struct __iterator_traits; + +template +struct iterator_traits : __iterator_traits<_Ip> { + using __primary_template = iterator_traits; +}; + +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 __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; +}; + +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 __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; +}; + +// [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 = + !__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 __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; +}; + +// 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 __iterator_traits {}; +#else template struct __iterator_traits {}; +template struct __iterator_traits_impl {}; + +template +struct __iterator_traits_impl<_Iter, true> +{ + typedef typename _Iter::difference_type difference_type; + typedef typename _Iter::value_type value_type; + typedef typename _Iter::pointer pointer; + typedef typename _Iter::reference reference; + typedef typename _Iter::iterator_category iterator_category; +}; + template struct __iterator_traits<_Iter, true> : __iterator_traits_impl @@ -737,8 +893,12 @@ using __primary_template = iterator_traits; }; +#endif // !defined(_LIBCPP_HAS_NO_RANGES) template +#if !defined(_LIBCPP_HAS_NO_RANGES) +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.compile.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp @@ -0,0 +1,258 @@ +//===----------------------------------------------------------------------===// +// +// 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()); 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,125 @@ +//===----------------------------------------------------------------------===// +// +// 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 { + decltype(std::declval().operator->()) operator->() const; +}; + +// 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 difference_type = typename std::incrementable_traits::difference_type; + using value_type = typename std::indirectly_readable_traits::value_type; + + using legacy_iterator::legacy_iterator; + 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; +}; + +// 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