diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -421,6 +421,7 @@ __iterator/advance.h __iterator/back_insert_iterator.h __iterator/bounded_iter.h + __iterator/check_iterators.h __iterator/common_iterator.h __iterator/concepts.h __iterator/counted_iterator.h diff --git a/libcxx/include/__algorithm/pstl_any_all_none_of.h b/libcxx/include/__algorithm/pstl_any_all_none_of.h --- a/libcxx/include/__algorithm/pstl_any_all_none_of.h +++ b/libcxx/include/__algorithm/pstl_any_all_none_of.h @@ -12,6 +12,7 @@ #include <__algorithm/pstl_find.h> #include <__algorithm/pstl_frontend_dispatch.h> #include <__config> +#include <__iterator/check_iterators.h> #include <__iterator/iterator_traits.h> #include <__type_traits/enable_if.h> #include <__type_traits/is_execution_policy.h> @@ -36,6 +37,7 @@ enable_if_t, int> = 0> _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool any_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); return std::__pstl_frontend_dispatch( _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_any_of), [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) { @@ -56,6 +58,7 @@ enable_if_t, int> = 0> _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool all_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); return std::__pstl_frontend_dispatch( _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_all_of), [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred) { @@ -78,6 +81,7 @@ enable_if_t, int> = 0> _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool none_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); return std::__pstl_frontend_dispatch( _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_none_of), [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred) { diff --git a/libcxx/include/__algorithm/pstl_fill.h b/libcxx/include/__algorithm/pstl_fill.h --- a/libcxx/include/__algorithm/pstl_fill.h +++ b/libcxx/include/__algorithm/pstl_fill.h @@ -13,6 +13,7 @@ #include <__algorithm/pstl_for_each.h> #include <__algorithm/pstl_frontend_dispatch.h> #include <__config> +#include <__iterator/check_iterators.h> #include <__iterator/iterator_traits.h> #include <__type_traits/is_execution_policy.h> #include <__type_traits/remove_cvref.h> @@ -36,6 +37,7 @@ enable_if_t, int> = 0> _LIBCPP_HIDE_FROM_ABI void fill(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); std::__pstl_frontend_dispatch( _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill), [&](_ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_value) { @@ -59,6 +61,7 @@ enable_if_t, int> = 0> _LIBCPP_HIDE_FROM_ABI void fill_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _SizeT __n, const _Tp& __value) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); std::__pstl_frontend_dispatch( _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill_n), [&](_ForwardIterator __g_first, _SizeT __g_n, const _Tp& __g_value) { diff --git a/libcxx/include/__algorithm/pstl_find.h b/libcxx/include/__algorithm/pstl_find.h --- a/libcxx/include/__algorithm/pstl_find.h +++ b/libcxx/include/__algorithm/pstl_find.h @@ -14,6 +14,7 @@ #include <__algorithm/pstl_backend.h> #include <__algorithm/pstl_frontend_dispatch.h> #include <__config> +#include <__iterator/check_iterators.h> #include <__iterator/iterator_traits.h> #include <__type_traits/is_execution_policy.h> #include <__type_traits/remove_cvref.h> @@ -34,6 +35,7 @@ enable_if_t, int> = 0> _LIBCPP_HIDE_FROM_ABI _ForwardIterator find_if(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); using _Backend = typename __select_backend<_RawPolicy>::type; return std::__pstl_find_if<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__pred)); } @@ -48,6 +50,7 @@ enable_if_t, int> = 0> _LIBCPP_HIDE_FROM_ABI _ForwardIterator find_if_not(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); return std::__pstl_frontend_dispatch( _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_find_if_not), [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) { @@ -70,6 +73,7 @@ enable_if_t, int> = 0> _LIBCPP_HIDE_FROM_ABI _ForwardIterator find(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); return std::__pstl_frontend_dispatch( _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_find), [&](_ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_value) { diff --git a/libcxx/include/__algorithm/pstl_for_each.h b/libcxx/include/__algorithm/pstl_for_each.h --- a/libcxx/include/__algorithm/pstl_for_each.h +++ b/libcxx/include/__algorithm/pstl_for_each.h @@ -14,6 +14,7 @@ #include <__algorithm/pstl_backend.h> #include <__algorithm/pstl_frontend_dispatch.h> #include <__config> +#include <__iterator/check_iterators.h> #include <__iterator/iterator_traits.h> #include <__type_traits/is_execution_policy.h> #include <__type_traits/remove_cvref.h> @@ -35,6 +36,7 @@ enable_if_t, int> = 0> _LIBCPP_HIDE_FROM_ABI void for_each(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Function __func) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); using _Backend = typename __select_backend<_RawPolicy>::type; std::__pstl_for_each<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__func)); } @@ -50,6 +52,7 @@ enable_if_t, int> = 0> _LIBCPP_HIDE_FROM_ABI void for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); return std::__pstl_frontend_dispatch( _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_for_each_n), [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) { diff --git a/libcxx/include/__algorithm/pstl_transform.h b/libcxx/include/__algorithm/pstl_transform.h --- a/libcxx/include/__algorithm/pstl_transform.h +++ b/libcxx/include/__algorithm/pstl_transform.h @@ -11,6 +11,7 @@ #include <__algorithm/pstl_backend.h> #include <__config> +#include <__iterator/check_iterators.h> #include <__iterator/iterator_traits.h> #include <__type_traits/is_execution_policy.h> #include <__utility/terminate_on_exception.h> @@ -35,6 +36,8 @@ _ForwardIterator __last, _ForwardOutIterator __result, _UnaryOperation __op) { + std::__check_forward_iterator_requirements<_ForwardIterator>(); + std::__check_forward_iterator_requirements<_ForwardOutIterator>(); using _Backend = typename __select_backend<_RawPolicy>::type; return std::__pstl_transform<_RawPolicy>( _Backend{}, std::move(__first), std::move(__last), std::move(__result), std::move(__op)); @@ -54,6 +57,9 @@ _ForwardIterator2 __first2, _ForwardOutIterator __result, _BinaryOperation __op) { + std::__check_forward_iterator_requirements<_ForwardIterator1>(); + std::__check_forward_iterator_requirements<_ForwardIterator2>(); + std::__check_forward_iterator_requirements<_ForwardOutIterator>(); using _Backend = typename __select_backend<_RawPolicy>::type; return std::__pstl_transform<_RawPolicy>( _Backend{}, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__result), std::move(__op)); diff --git a/libcxx/include/__iterator/check_iterators.h b/libcxx/include/__iterator/check_iterators.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/check_iterators.h @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// 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_CHECK_ITERATORS_H +#define _LIBCPP___ITERATOR_CHECK_ITERATORS_H + +#include <__config> +#include <__type_traits/integral_constant.h> +#include <__type_traits/is_copy_assignable.h> +#include <__type_traits/is_copy_constructible.h> +#include <__type_traits/is_default_constructible.h> +#include <__type_traits/is_destructible.h> +#include <__type_traits/is_equality_comparable.h> +#include <__type_traits/is_move_assignable.h> +#include <__type_traits/is_move_constructible.h> +#include <__type_traits/is_same.h> +#include <__type_traits/is_swappable.h> +#include <__type_traits/void_t.h> +#include <__utility/declval.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct __has_dereference_operator : false_type {}; + +template +struct __has_dereference_operator<_Tp, __void_t())> > : true_type {}; + +template +struct __has_preincrement : false_type {}; + +template +struct __has_preincrement<_Tp, __void_t())> > : true_type {}; + +template +struct __has_not_equal : false_type {}; + +template +struct __has_not_equal<_Tp, __void_t() != std::declval<_Tp>())> > : true_type {}; + +template +_LIBCPP_CONSTEXPR void __check_iterator_requirements() { + static_assert(__has_dereference_operator<_Iterator&>::value, "Iterator has to be dereferenceable"); + static_assert(__has_preincrement<_Iterator&>::value, "Iterator must have a preincrement (++) operator"); + static_assert(is_same<_Iterator&, decltype(++std::declval<_Iterator&>())>::value, + "The preincrement operator must return Iterator&"); + static_assert(is_move_constructible<_Iterator>::value, "Iterator must be move constructible"); + static_assert(is_copy_constructible<_Iterator>::value, "Iterator must be copy constructible"); + static_assert(is_move_assignable<_Iterator>::value, "Iterator must be move assignable"); + static_assert(is_copy_assignable<_Iterator>::value, "Iterator must be copy assignable"); + static_assert(is_swappable<_Iterator>::value, "Iterator must be swappable"); +} + +template +_LIBCPP_CONSTEXPR void __check_input_iterator_requirements() { + std::__check_iterator_requirements<_Iterator>(); + static_assert(__is_equality_comparable<_Iterator&, _Iterator&>::value, "Iterator must implement operator=="); + static_assert(__has_not_equal<_Iterator&>::value, "Iterator must implement operator!="); +} + +template +_LIBCPP_CONSTEXPR void __check_forward_iterator_requirements() { + std::__check_input_iterator_requirements<_Iterator>(); + static_assert(is_default_constructible<_Iterator>::value, "Iterator must be default constructible"); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ITERATOR_CHECK_ITERATORS_H diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -1069,6 +1069,7 @@ export concepts.equality_comparable export type_traits.common_reference } + module check_iterators { private header "__iterator/check_iterators.h" } module counted_iterator { private header "__iterator/counted_iterator.h" } module data { private header "__iterator/data.h" } module default_sentinel { private header "__iterator/default_sentinel.h" } diff --git a/libcxx/test/libcxx/algorithms/iterator_requirements.verify.cpp b/libcxx/test/libcxx/algorithms/iterator_requirements.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/algorithms/iterator_requirements.verify.cpp @@ -0,0 +1,106 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// Check that __check_*_iterator_requirements catch bad iterators + +// ADDITIONAL_COMPILE_FLAGS: -Wno-private-header + +#include <__iterator/check_iterators.h> + +struct missing_preincrement { + int& operator*(); +}; + +template +struct valid_iterator { + int& operator*(); + Derived& operator++(); +}; + +struct not_move_constructible : valid_iterator { + not_move_constructible(const not_move_constructible&) = default; + not_move_constructible(not_move_constructible&&) = delete; + not_move_constructible& operator=(not_move_constructible&&) = default; + not_move_constructible& operator=(const not_move_constructible&) = default; +}; +void swap(not_move_constructible&, not_move_constructible&); + +struct not_copy_constructible : valid_iterator { + not_copy_constructible(const not_copy_constructible&) = delete; + not_copy_constructible(not_copy_constructible&&) = default; + not_copy_constructible& operator=(not_copy_constructible&&) = default; + not_copy_constructible& operator=(const not_copy_constructible&) = default; +}; + +struct not_move_assignable : valid_iterator { + not_move_assignable(const not_move_assignable&) = default; + not_move_assignable(not_move_assignable&&) = default; + not_move_assignable& operator=(not_move_assignable&&) = delete; + not_move_assignable& operator=(const not_move_assignable&) = default; +}; +void swap(not_move_assignable&, not_move_assignable&); + +struct not_copy_assignable : valid_iterator { + not_copy_assignable(const not_copy_assignable&) = default; + not_copy_assignable(not_copy_assignable&&) = default; + not_copy_assignable& operator=(not_copy_assignable&&) = default; + not_copy_assignable& operator=(const not_copy_assignable&) = delete; +}; + +struct not_swappable : valid_iterator {}; +void swap(not_swappable&, not_swappable&) = delete; + +void check_iterator_requirements() { + // expected-error@*:* {{Iterator has to be dereferenceable}} + std::__check_iterator_requirements(); // expected-note {{here}} + + // expected-error@*:* {{cannot increment value of type 'missing_preincrement'}} + // expected-error@*:* {{Iterator must have a preincrement (++) operator}} + std::__check_iterator_requirements(); // expected-note {{here}} + + // expected-error@*:* {{Iterator must be move constructible}} + std::__check_iterator_requirements(); // expected-note {{here}} + + // expected-error@*:* {{Iterator must be copy constructible}} + std::__check_iterator_requirements(); // expected-note {{here}} + + // expected-error@*:* {{Iterator must be move assignable}} + std::__check_iterator_requirements(); // expected-note {{here}} + + // expected-error@*:* {{Iterator must be copy assignable}} + std::__check_iterator_requirements(); // expected-note {{here}} + + // expected-error@*:* {{Iterator must be swappable}} + std::__check_iterator_requirements(); // expected-note {{here}} +} + +struct not_equality_comparable : valid_iterator {}; +bool operator!=(not_equality_comparable, not_equality_comparable); + +struct not_unequality_comparable : valid_iterator {}; +bool operator==(not_unequality_comparable, not_unequality_comparable); +bool operator!=(not_unequality_comparable, not_unequality_comparable) = delete; + +void check_input_iterator_requirements() { + // expected-error@*:* {{Iterator must implement operator==}} + std::__check_input_iterator_requirements(); // expected-note {{here}} + + // expected-error@*:* {{Iterator must implement operator!=}} + std::__check_input_iterator_requirements(); // expected-note {{here}} +} + +struct not_default_constructible : valid_iterator { + not_default_constructible() = delete; +}; +bool operator==(not_default_constructible, not_default_constructible); +bool operator!=(not_default_constructible, not_default_constructible); + +void check_forward_iterator_requirements() { + // expected-error@*:* {{Iterator must be default constructible}} + std::__check_forward_iterator_requirements(); // expected-note {{here}} +}