Skip to content

Instantly share code, notes, and snippets.

@ericniebler

ericniebler/merge2std.cpp

Last active June 1, 2018 17:51
Show Gist options
  • Save ericniebler/d07bfb0d8ebf2e25f94f2111f893ec30 to your computer and use it in GitHub Desktop.
Save ericniebler/d07bfb0d8ebf2e25f94f2111f893ec30 to your computer and use it in GitHub Desktop.
Download ZIP
iterator traits and tags redesign for merging the Ranges TS
Raw
merge2std.cpp
// Copyright 2018-present Eric Niebler
// Copyright 2018-present Facebook, Inc
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// This is a PROTOTYPE and EXAMPLE of how the iterator concepts and traits from
// the Ranges TS might be merged into a future version of the _C++ standard. Don't
// expect anything in here to be bug-free.
extern "C" int printf(char const*, ...);
namespace std
{
template <class _T>
concept bool _AnyType = true;
template <template <class...> class _T, class... _Us>
concept bool _Valid = requires { typename _T<_Us...>; };
template <class _T, class _U>
concept bool _Same = __is_same_as(_T, _U);
template <class _T>
using __t = typename _T::type;
template <class _F, class... _As>
using __invoke = typename _F::template __invoke<_As...>;
template <bool>
struct __select_ {
template <class _Else, template <class...> class, class...>
using __invoke = _Else;
};
template <>
struct __select_<true> {
template <class, template <class...> class _T, class... _Us>
using __invoke = _T<_Us...>;
};
template <class _Else, template <class...> class _T, class... _Us>
using __select =
typename __select_<_Valid<_T, _Us...>>::
template __invoke<_Else, _T, _Us...>;
template <class _T>
constexpr _T* const __nullptr_v = nullptr;
// cstddef
using ptrdiff_t = decltype(__nullptr_v<char> - __nullptr_v<char>);
using size_t = decltype(sizeof(ptrdiff_t));
// type_traits:
template <bool _B>
inline constexpr bool __not = !_B;
template <class _T>
struct type_identity {
using type = _T;
};
template <int _N> struct __priority : __priority<_N - 1> { };
template <> struct __priority<0> { };
template <_AnyType _T, _T = 1>
constexpr bool __can_one() { return true; }
template <class _T>
constexpr bool __can_one() { return false; }
template <class _T>
inline constexpr bool is_integral_v = __can_one<_T>();
template <class _T>
inline constexpr bool is_signed_v = false;
template <class _T>
requires is_integral_v<_T>
inline constexpr bool is_signed_v<_T> = _T(-1) < _T(0);
template <class _T>
struct make_signed { using type = _T; }; // BUGBUG
template <class _T>
struct remove_cv { using type = _T; };
template <class _T>
struct remove_cv<const _T> { using type = _T; };
template <class _T>
struct remove_cv<volatile _T> { using type = _T; };
template <class _T>
struct remove_cv<const volatile _T> { using type = _T; };
template <class _T>
using remove_cv_t = __t<remove_cv<_T>>;
template <class _T>
struct remove_reference { using type = _T; };
template <class _T>
struct remove_reference<_T &> { using type = _T; };
template <class _T>
struct remove_reference<_T &&> { using type = _T; };
template <class _T>
using remove_reference_t = __t<remove_reference<_T>>;
template <class _T>
using __add_lvalue_reference = _T &;
template <class _T>
using add_lvalue_reference_t = __select<_T, __add_lvalue_reference, _T>;
template <class _T>
using __add_rvalue_reference = _T &&;
template <class _T>
using add_rvalue_reference_t = __select<_T, __add_rvalue_reference, _T>;
template <class _T>
using remove_cvref_t = remove_cv_t<remove_reference_t<_T>>;
// declval:
template <_AnyType _T> _T && declval() noexcept;
template <class _T> void declval() noexcept;
template <bool>
struct __conditional {
template <class, class _U> using __invoke = _U;
};
template <>
struct __conditional<true> {
template <class _T, class> using __invoke = _T;
};
template <bool _B, class _T, class _U>
using conditional_t = __invoke<__conditional<_B>, _T, _U>;
struct __empty { };
template <bool _B, class _T = void>
using enable_if = conditional_t<_B, type_identity<_T>, __empty>;
template <class _T>
using add_pointer_t = remove_reference_t<_T> *;
template <class _T, class _U>
inline constexpr bool is_same_v = __is_same_as(_T, _U);
template <class _T, class _U>
inline constexpr bool is_base_of_v = __is_base_of(_T, _U);
template <class _T>
inline constexpr bool is_const_v = false;
template <class _T>
inline constexpr bool is_const_v<const _T> = true;
template <class _T>
inline constexpr bool is_reference_v = !is_same_v<remove_reference_t<_T>, _T>;
template <class _T>
inline constexpr bool is_array_v = false;
template <class _T>
inline constexpr bool is_array_v<_T[]> = true;
template <class _T, size_t _N>
inline constexpr bool is_array_v<_T[_N]> = true;
template <class _T>
inline constexpr bool is_function_v =
!is_const_v<_T> && !is_reference_v<_T> && is_same_v<_T, const _T>;
template <class _T>
inline constexpr bool is_void_v = is_same_v<void, remove_cv_t<_T>>;
template <class _T>
inline constexpr bool is_object_v =
!is_reference_v<_T> && !is_void_v<_T> && !is_function_v<_T>;
template <class _T> _T *__decay_fn(_T (&)[]);
template <class _T, size_t _N> _T *__decay_fn(_T (&)[_N]);
template <class _T, class..._As> _T (*__decay_fn(_T(&)(_As...)))(_As...);
template <class _T> using __decay_t = decltype(__decay_fn(declval<_T &>()));
template <class _T>
using decay_t = __select<remove_cvref_t<_T>, __decay_t, _T>;
template <class _T>
using decay = type_identity<decay_t<_T>>;
template <class From, class To>
inline constexpr bool is_convertible_v = is_void_v<From> && is_void_v<To>;
template <class From, class To>
requires requires (From &&(&from)(), void(&to)(To)) { to(from()); }
inline constexpr bool is_convertible_v<From, To> = true;
template <class _T>
using __cref = add_lvalue_reference_t<const remove_reference_t<_T>>;
template <class _T, class _U>
using __cond = decltype(true ? ((_T(*)())0)() : ((_U(*)())0)());
template <class From>
struct __copy_cv_ { template <class To> using __invoke = To; };
template <class From>
struct __copy_cv_<const From> { template <class To> using __invoke = const To; };
template <class From>
struct __copy_cv_<volatile From> { template <class To> using __invoke = volatile To; };
template <class From>
struct __copy_cv_<const volatile From> { template <class To> using __invoke = const volatile To; };
template <class From, class To>
using __copy_cv = __invoke<__copy_cv_<From>, To>;
template <class _T, class _U>
struct __builtin_common { };
template <class _T, class _U>
using __builtin_common_t = __t<__builtin_common<_T, _U>>;
template <class _T, class _U>
requires _Valid<__cond, __cref<_T>, __cref<_U>>
struct __builtin_common<_T, _U> : decay<__cond<__cref<_T>, __cref<_U>>> { };
template <class _T, class _U, class _R = __builtin_common_t<_T &, _U &>>
using __rref_res =
conditional_t<is_reference_v<_R>, remove_reference_t<_R> &&, _R>;
template <class _T, class _U>
requires _Valid<__builtin_common_t, _T &, _U &> &&
requires (_T && t, _U && u) {
{ (_T &&) t } -> __rref_res<_T, _U>;
{ (_U &&) u } -> __rref_res<_T, _U>;
}
struct __builtin_common<_T &&, _U &&> { using type = __rref_res<_T, _U>; };
template <class _T, class _U>
using __lref_res = __cond<__copy_cv<_T, _U> &, __copy_cv<_U, _T> &>;
template <class _T, class _U>
struct __builtin_common<_T &, _U &> { };
template <class _T, class _U>
requires _Valid<__lref_res, _T, _U>
struct __builtin_common<_T &, _U &> { using type = __lref_res<_T, _U>; };
template <class _T, class _U>
requires _Valid<__builtin_common_t, _T &, const _U &> &&
requires (_U && u) {
{ (_U &&) u } -> __builtin_common_t<_T &, const _U &>;
}
struct __builtin_common<_T &, _U &&> : __builtin_common<_T &, const _U &> { };
template <class _T, class _U>
struct __builtin_common<_T &&, _U &> : __builtin_common<_U &, _T &&> { };
// common_type
template <class...>
struct common_type { };
template <class... Ts>
using common_type_t = __t<common_type<Ts...>>;
template <class _T>
struct common_type<_T> : decay<_T> { };
template <class _T, class _U>
struct __common_type2 : common_type<decay_t<_T>, decay_t<_U>> { };
template <class _T>
concept bool _Decayed = __is_same_as(_T, decay_t<_T>);
template <_Decayed _T, _Decayed _U>
struct __common_type2<_T, _U> : __builtin_common<_T, _U> { };
template <_Decayed _T, _Decayed _U>
requires _Valid<__cond, _T, _U>
struct __common_type2<_T, _U> : decay<__cond<_T, _U>> { };
template <class _T, class _U>
struct common_type<_T, _U> : __common_type2<_T, _U> { };
template <class _T, class _U, class _V, class... _W>
requires _Valid<common_type_t, _T, _U>
struct common_type<_T, _U, _V, _W...>
: common_type<common_type_t<_T, _U>, _V, _W...> { };
template <class _T>
struct __copy_cvref_ : __copy_cv_<_T> { };
template <class _T>
struct __copy_cvref_<_T &> {
template <class _U>
using __invoke = add_lvalue_reference_t<__copy_cv<_T, _U>>;
};
template <class _T>
struct __copy_cvref_<_T &&> {
template <class _U>
using __invoke = add_rvalue_reference_t<__copy_cv<_T, _U>>;
};
template <class _T, class _U, template <class> class TQual, template <class> class UQual>
struct basic_common_reference { };
template <class _T, class _U>
using __basic_common_reference =
basic_common_reference<remove_cvref_t<_T>, remove_cvref_t<_U>,
__copy_cvref_<_T>::template __invoke,
__copy_cvref_<_U>::template __invoke>;
// common_reference
template <class...>
struct common_reference { };
template <class... Ts>
using common_reference_t = __t<common_reference<Ts...>>;
template <class _T>
struct common_reference<_T> { using type = _T; };
template <class _T, class _U>
common_type<_T, _U> __common_reference2_fn(__priority<0>);
template <class _T, class _U>
type_identity<__cond<_T, _U>> __common_reference2_fn(__priority<1>);
template <class _T, class _U>
requires _Valid<__t, __basic_common_reference<_T, _U>>
__basic_common_reference<_T, _U> __common_reference2_fn(__priority<2>);
template <class _T, class _U>
requires __is_same_as(_T &&, _T) && __is_same_as(_U &&, _U) &&
__is_same_as(__builtin_common_t<_T, _U> &&, __builtin_common_t<_T, _U>)
__builtin_common<_T, _U> __common_reference2_fn(__priority<3>);
template <class _T, class _U>
struct common_reference<_T, _U>
: decltype(__common_reference2_fn<_T, _U>(__priority<3>{})) { };
template <class _T, class _U, class _V, class... _W>
requires _Valid<common_reference_t, _T, _U>
struct common_reference<_T, _U, _V, _W...>
: common_reference<common_reference_t<_T, _U>, _V, _W...> { };
// Concepts
template <class _T, class _U>
concept bool Same = _Same<_T, _U> && _Same<_U, _T>;
template <class _T>
concept bool Integral = is_integral_v<_T>;
template <class _T>
concept bool SignedIntegral = Integral<_T> && is_signed_v<_T>;
template <class From, class To>
concept bool ConvertibleTo =
is_convertible_v<From, To> && requires (From(&from)()) {
static_cast<To>(from());
};
template <class _T, class _U>
concept bool CommonReference =
requires {
typename common_reference_t<_T, _U>;
typename common_reference_t<_U, _T>;
} &&
Same<common_reference_t<_T, _U>, common_reference_t<_U, _T>> &&
ConvertibleTo<_T, common_reference_t<_T, _U>> &&
ConvertibleTo<_U, common_reference_t<_T, _U>>;
template <class _T, class _U>
concept bool Common =
requires {
typename common_type_t<_T, _U>;
typename common_type_t<_U, _T>;
} &&
Same<common_type_t<_T, _U>, common_type_t<_U, _T>> &&
ConvertibleTo<_T, common_type_t<_T, _U>> &&
ConvertibleTo<_U, common_type_t<_T, _U>> &&
CommonReference<add_lvalue_reference_t<const _T>,
add_lvalue_reference_t<const _U>> &&
CommonReference<add_lvalue_reference_t<common_type_t<_T, _U>>,
common_reference_t<add_lvalue_reference_t<const _T>,
add_lvalue_reference_t<const _U>>>;
template <class _T, class... Args>
concept bool Constructible = __is_constructible(_T, Args...);
template <class _T, class _U>
concept bool Assignable =
Same<_T &, _T> && CommonReference<__cref<_T>, __cref<_U>> &&
requires (_T t, _U && u) {
{ t = (_U &&) u } -> Same<_T> &&;
};
template <class _T>
concept bool Movable = is_object_v<_T> && Constructible<_T, _T> &&
Assignable<_T &, _T> && ConvertibleTo<_T, _T>;
template <class _T>
concept bool Copyable = Movable<_T> && Constructible<_T, const _T &> &&
Assignable<_T &, const _T &> && ConvertibleTo<const _T &, _T>;
template <class _T>
concept bool Semiregular = Constructible<_T> && Copyable<_T>;
template <class _T, class _U>
concept bool _WeaklyEqualityComparableWith =
requires (__cref<_T> a, __cref<_U> b) {
{a == b} -> bool;
{a != b} -> bool;
{b == a} -> bool;
{b != a} -> bool;
};
template <class _T>
concept bool EqualityComparable = _WeaklyEqualityComparableWith<_T, _T>;
template <class _T>
concept bool Regular = Semiregular<_T> && EqualityComparable<_T>;
template <class _T>
concept bool StrictTotallyOrdered =
EqualityComparable<_T> &&
requires (__cref<_T> a, __cref<_T> b) {
{ a < b } -> bool;
{ a > b } -> bool;
{ a <= b } -> bool;
{ a >= b } -> bool;
};
template <class _T>
constexpr _T && move(_T & t) noexcept {
return static_cast<_T &&>(t);
}
struct output_iterator_tag { };
struct input_iterator_tag { };
struct forward_iterator_tag : input_iterator_tag { };
struct bidirectional_iterator_tag : forward_iterator_tag { };
struct random_access_iterator_tag : bidirectional_iterator_tag { };
struct contiguous_iterator_tag : random_access_iterator_tag { };
template <template <class> class _Trait, class _T>
concept bool _IsPrimary = _Same<typename _Trait<_T>::__primary, _T>;
template <class _T>
struct iterator_traits;
template <class _T> using __difference_type = typename _T::difference_type;
template <class _T> using __value_type = typename _T::value_type;
template <class _T> using __reference = typename _T::reference;
template <class _T> using __pointer = typename _T::pointer;
template <class _T> using __iterator_category = typename _T::iterator_category;
template <class _T> using __iterator_concept = typename _T::iterator_concept;
namespace ranges {
template <class _T>
struct incrementable_traits { };
template <class _T>
using iter_difference_t =
__difference_type<conditional_t<
_IsPrimary<iterator_traits, _T>,
incrementable_traits<_T>,
iterator_traits<_T>>>;
template <class _T>
struct readable_traits { };
template <class _T>
using iter_value_t =
__value_type<conditional_t<
_IsPrimary<iterator_traits, _T>,
readable_traits<_T>,
iterator_traits<_T>>>;
template <class _I>
requires requires(_I &i) { { *i } -> _AnyType &&; }
using iter_reference_t = decltype(*declval<_I &>());
}
using ranges::iter_value_t;
using ranges::iter_difference_t;
using ranges::iter_reference_t;
template <class _I>
concept bool _Cpp98Iterator =
Copyable<_I> && requires (_I i) {
{ *i } -> _AnyType &&;
{ ++i } -> Same<_I> &;
{ *i++ } -> _AnyType &&;
};
template <class _T, class _U>
concept bool _HasCommonReference = _Valid<common_reference_t, _T &&, _U &&>;
template <class _I>
using __readable_value_type = __value_type<ranges::readable_traits<_I>>;
template <class _I>
concept bool _Cpp98InputIterator =
_Cpp98Iterator<_I> && EqualityComparable<_I> && requires (_I i) {
{ *i } -> _HasCommonReference<__readable_value_type<_I> &> &&;
{ *i++ } -> _HasCommonReference<__readable_value_type<_I> &> &&;
} && SignedIntegral<__difference_type<ranges::incrementable_traits<_I>>>;
template <class _I>
concept bool _Cpp98ForwardIterator =
_Cpp98InputIterator<_I> && Constructible<_I> &&
Same<__value_type<ranges::readable_traits<_I>>,
remove_cvref_t<iter_reference_t<_I>>> &&
requires (_I i) {
{ i++ } -> const _I &;
requires Same<iter_reference_t<_I>, decltype(*i++)>;
};
template <class _I>
concept bool _Cpp98BidirectionalIterator =
_Cpp98ForwardIterator<_I> &&
requires (_I i) {
{ --i } -> Same<_I> &;
{ i-- } -> const _I &;
requires Same<iter_reference_t<_I>, decltype(*i--)>;
};
template <class _I>
concept bool _Cpp98RandomAccessIterator =
_Cpp98BidirectionalIterator<_I> && StrictTotallyOrdered<_I> &&
requires (_I i, __difference_type<ranges::incrementable_traits<_I>> n) {
{ i += n } -> Same<_I> &;
{ i -= n } -> Same<_I> &;
requires Same<_I, decltype(i + n)>;
requires Same<_I, decltype(n + i)>;
requires Same<_I, decltype(i - n)>;
requires Same<decltype(n), decltype(i - i)>;
{ i[n] } -> iter_reference_t<_I>;
};
template <class _I>
auto __pointer_fn(__priority<3>) -> __pointer<_I>;
template <class _I>
auto __pointer_fn(__priority<2>) -> decltype(declval<_I &>().operator->());
template <class _I>
requires Same<iter_reference_t<_I> &, iter_reference_t<_I>>
auto __pointer_fn(__priority<1>) -> add_pointer_t<iter_reference_t<_I>>;
template <class>
auto __pointer_fn(__priority<0>) -> void;
template <class _I>
auto __iterator_category_fn(__priority<4>) -> __iterator_category<_I>;
template <_Cpp98RandomAccessIterator _I>
auto __iterator_category_fn(__priority<3>) -> random_access_iterator_tag;
template <_Cpp98BidirectionalIterator _I>
auto __iterator_category_fn(__priority<2>) -> bidirectional_iterator_tag;
template <_Cpp98ForwardIterator _I>
auto __iterator_category_fn(__priority<1>) -> forward_iterator_tag;
template <_Cpp98InputIterator _I>
auto __iterator_category_fn(__priority<0>) -> input_iterator_tag;
template <class _I>
concept bool _HasIteratorTypes =
requires {
typename _I::difference_type;
typename _I::value_type;
typename _I::reference;
typename _I::iterator_category;
};
template <class _T>
struct __iterator_traits_impl_2 { };
template <_Cpp98Iterator _I>
struct __iterator_traits_impl_2<_I> {
using difference_type =
__select<void, __difference_type, ranges::incrementable_traits<_I>>;
using value_type = void;
using reference = void;
using pointer = void;
using iterator_category = output_iterator_tag;
};
template <_Cpp98InputIterator _I>
struct __iterator_traits_impl_2<_I> {
using difference_type = __difference_type<ranges::incrementable_traits<_I>>;
using value_type = __value_type<ranges::readable_traits<_I>>;
using reference = __select<iter_reference_t<_I>, __reference, _I>;
using pointer = decltype(__pointer_fn<_I>(__priority<3>{}));
using iterator_category = decltype(__iterator_category_fn<_I>(__priority<4>{}));
};
template <class _I>
struct __iterator_traits_impl : __iterator_traits_impl_2<_I> { };
template <_HasIteratorTypes _I>
struct __iterator_traits_impl<_I> {
using difference_type = __difference_type<_I>;
using value_type = __value_type<_I>;
using reference = __reference<_I>;
using pointer = __select<void, __pointer, _I>;
using iterator_category = __iterator_category<_I>;
};
template <class _I>
struct iterator_traits : __iterator_traits_impl<_I> {
using __primary = _I;
};
template <class _T>
struct iterator_traits<_T *> {
using difference_type = ptrdiff_t;
using value_type = remove_cv_t<_T>;
using pointer = _T *;
using reference = _T &;
using iterator_category = random_access_iterator_tag;
using iterator_concept = contiguous_iterator_tag;
};
namespace ranges {
template <class _T>
struct incrementable_traits<_T *> { };
template <class _T>
requires is_object_v<_T>
struct incrementable_traits<_T *> {
using difference_type = ptrdiff_t;
};
template <class _I>
struct incrementable_traits<const _I>
: incrementable_traits<decay_t<_I>> { };
template <class _T>
requires _Valid<__difference_type, _T>
struct incrementable_traits<_T> {
using difference_type = __difference_type<_T>;
};
template <class _T>
requires !_Valid<__difference_type, _T> &&
requires(const _T &a, const _T &b) {
a - b;
requires Integral<decltype(a - b)>;
}
struct incrementable_traits<_T> {
using difference_type =
__t<make_signed<decltype(declval<_T>() - declval<_T>())>>;
};
template <class _T>
struct __with_value_type { using value_type = _T; };
template <class _T>
using __if_is_object =
conditional_t<is_object_v<_T>, __with_value_type<_T>, __empty>;
template <class _T>
struct readable_traits<_T *> : __if_is_object<remove_cv_t<_T>> { };
template <class _I>
requires is_array_v<_I>
struct readable_traits<_I> : readable_traits<decay_t<_I>> { };
template <class _I>
struct readable_traits<const _I> : readable_traits<decay_t<_I>> { };
template <class _T>
requires _Valid<__value_type, _T>
struct readable_traits<_T> : __if_is_object<__value_type<_T>> { };
template <class _T>
requires requires { typename _T::element_type; }
struct readable_traits<_T>
: __if_is_object<remove_cv_t<typename _T::element_type>> { };
namespace __iter_move {
template <class _T>
requires _Valid<iter_reference_t, _T>
constexpr decltype(auto) iter_move(_T && t) noexcept(noexcept(*t)) {
if constexpr (is_same_v<iter_reference_t<_T> &, iter_reference_t<_T>>)
return move(*t);
else
return *t;
}
struct __fn {
template <class _T>
requires requires (_T && t) {
{ iter_move((_T &&) t) } -> _AnyType &&;
}
constexpr decltype(auto) operator()(_T && t) const
noexcept(noexcept(iter_move((_T &&)t))) {
return iter_move((_T &&)t);
}
};
}
namespace {
inline constexpr __iter_move::__fn iter_move { };
}
template <class _T>
requires requires (_T & t) { iter_move(t); }
using iter_rvalue_reference_t = decltype(iter_move(declval<_T &>()));
// In the case of accidental conformance of new-style (no nested
// ::iterator_category) iterators, the user may opt-out of conformance
// to an iterator concept by specializing iterator_traits for their type
// and specifying iterator_concept there. The need for this override
// should be rare.
// Why "iterator_concept" instead of "iterator_category". Given a
// new-style iterator that returns prvalues that is a ForwardIterator
// but accidentally conforms to BidirectionalIterator, there would be
// no way to opt out of BidirectionalIterator conformance without
// violating the requirements of generic STL1 code. An iterator_category
// of forward_iterator_tag would be untrue for legacy algorithms. An
// iterator_category of input_iterator_tag would pessimize new
// algorithms.
//
// If iterator_traits<_I> is not specialized, then we want to ignore the
// category tags as computed via syntactic conformance to the STL1
// iterator requirements tables. If `_I` is not a pointer,
// and `_I::iterator_category` is not a well-formed type, then just
// return "random_acceess_iterator_tag", which has the effect of turning
// the explicit conformance test into a no-op. That way, only syntactic
// conformance to the Ranges iterator concepts is considered.
template <class _I>
using __iter_traits_sel =
conditional_t<_IsPrimary<iterator_traits, _I>, _I, iterator_traits<_I>>;
template <class _I>
struct __iter_concept_impl : enable_if<
_IsPrimary<iterator_traits, _I>, random_access_iterator_tag> { };
template <class _I>
requires _Valid<__iterator_concept, __iter_traits_sel<_I>>
struct __iter_concept_impl<_I> {
using type = __iterator_concept<__iter_traits_sel<_I>>;
};
template <class _I>
requires _Valid<__iterator_category, __iter_traits_sel<_I>> &&
!_Valid<__iterator_concept, __iter_traits_sel<_I>>
struct __iter_concept_impl<_I>{
using type = __iterator_category<__iter_traits_sel<_I>>;
};
template <class _I>
using __iter_concept = __t<__iter_concept_impl<_I>>;
template <class _I>
concept bool Readable =
requires {
typename iter_value_t<_I>;
typename iter_reference_t<_I>;
typename iter_rvalue_reference_t<_I>;
} &&
CommonReference<iter_reference_t<_I> &&, iter_value_t<_I> &> &&
CommonReference<iter_reference_t<_I> &&, iter_rvalue_reference_t<_I> &&> &&
CommonReference<iter_rvalue_reference_t<_I> &&, const iter_value_t<_I> &>;
template <class _I>
concept bool WeaklyIncrementable =
Semiregular<_I> && requires (_I i) {
typename iter_difference_t<_I>;
{ ++i } -> Same<_I> &;
i++;
} && SignedIntegral<iter_difference_t<_I>>;
template <class _I>
concept bool Incrementable =
WeaklyIncrementable<_I> && EqualityComparable<_I> && requires (_I i) {
requires Same<_I, decltype(i++)>;
};
template <class _I>
concept bool Iterator =
WeaklyIncrementable<_I> && requires {
typename iter_reference_t<_I>;
};
template <class _S, class _I>
concept bool Sentinel =
Semiregular<_S> && Iterator<_I> &&
_WeaklyEqualityComparableWith<_S, _I>;
template <class _S, class _I>
inline constexpr bool disable_sized_sentinel = false;
template <class _S, class _I>
concept bool SizedSentinel =
Sentinel<_S, _I> &&
__not<disable_sized_sentinel<remove_cv_t<_S>, remove_cv_t<_I>>> &&
requires(const _I& i, const _S& s) {
s - i;
i - s;
requires Same<iter_difference_t<_I>, decltype(s - i)>;
requires Same<iter_difference_t<_I>, decltype(i - s)>;
};
template <class _I>
concept bool InputIterator =
Iterator<_I> && Readable<_I>;
template <class _I>
concept bool ForwardIterator =
__is_base_of(forward_iterator_tag, __iter_concept<_I>) &&
Incrementable<_I> && InputIterator<_I>;
template <class _I>
concept bool BidirectionalIterator =
__is_base_of(bidirectional_iterator_tag, __iter_concept<_I>) &&
ForwardIterator<_I> && requires (_I i) {
{ --i } -> Same<_I> &;
i--;
requires Same<_I, decltype(i--)>;
};
template <class _I>
concept bool RandomAccessIterator =
__is_base_of(random_access_iterator_tag, __iter_concept<_I>) &&
BidirectionalIterator<_I> &&
StrictTotallyOrdered<_I> &&
SizedSentinel<_I, _I> &&
requires(_I i, _I j, iter_difference_t<_I> n) {
{ i += n } -> Same<_I> &;
{ i -= n } -> Same<_I> &;
j + n;
n + j;
j - n;
j[n];
requires Same<decltype(j + n), _I>;
requires Same<decltype(n + j), _I>;
requires Same<decltype(j - n), _I>;
requires Same<decltype(j[n]), iter_reference_t<_I>>;
};
template <class _I>
concept bool ContiguousIterator =
__is_base_of(contiguous_iterator_tag, __iter_concept<_I>) &&
RandomAccessIterator<_I> &&
Same<iter_reference_t<_I> &, iter_reference_t<_I>> &&
requires (_I i) {
{ *i } -> Same<iter_value_t<_I>> const volatile &;
};
} // namespace ranges
}
////////////////////////////////////////////////////////////////////////////////
// TEST CODE
////////////////////////////////////////////////////////////////////////////////
struct _X {
int& operator*() const;
_X & operator++();
struct proxy { operator int() const; };
proxy operator++(int);
};
namespace std {
template <>
struct iterator_traits<::_X> {
using value_type = int;
using reference = int&;
using pointer = int*;
using difference_type = ptrdiff_t;
using iterator_category = input_iterator_tag;
};
};
static_assert(std::ranges::InputIterator<_X>);
struct _Y {
using value_type = int;
using difference_type = std::ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;
using reference = int&;
using pointer = int*;
int& operator*() const noexcept;
};
static_assert(std::is_same_v<std::add_pointer_t<int&>, int*>);
struct _Z {
using difference_type = std::ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;
int& operator*() const noexcept;
_Z& operator++();
_Z operator++(int);
bool operator==(_Z) const;
bool operator!=(_Z) const;
};
namespace std::ranges {
template <>
struct readable_traits<::_Z> {
using value_type = int;
};
}
// Looks like an STL2 forward iterator, but the conformance beyond
// input is "accidental".
struct WouldBeFwd {
using value_type = struct _S{ };
using difference_type = std::ptrdiff_t;
_S & operator*() const;
WouldBeFwd& operator++();
WouldBeFwd operator++(int);
//_S* operator->() const;
bool operator==(WouldBeFwd) const;
bool operator!=(WouldBeFwd) const;
};
namespace std {
template <>
struct iterator_traits<::WouldBeFwd> {
using value_type = typename ::WouldBeFwd::value_type;
using difference_type = typename ::WouldBeFwd::difference_type;
using reference = iter_reference_t<::WouldBeFwd>;
using pointer = add_pointer_t<reference>;
// Explicit opt-out of stl2's ForwardIterator concept:
using iterator_category = std::input_iterator_tag; // STL1-style iterator category
};
}
// Looks like an STL2 bidirectional iterator, but the conformance beyond
// forward is "accidental".
struct WouldBeBidi {
using value_type = struct _S{ };
using difference_type = std::ptrdiff_t;
// using iterator_category = std::input_iterator_tag;
// using iterator_concept = std::forward_iterator_tag;
_S operator*() const; // by value!
WouldBeBidi& operator++();
WouldBeBidi operator++(int);
WouldBeBidi& operator--();
WouldBeBidi operator--(int);
//_S* operator->() const;
bool operator==(WouldBeBidi) const;
bool operator!=(WouldBeBidi) const;
};
namespace std {
template <>
struct iterator_traits<::WouldBeBidi> {
using value_type = typename ::WouldBeBidi::value_type;
using difference_type = typename ::WouldBeBidi::difference_type;
using reference = value_type;
using pointer = value_type*;
using iterator_category = std::input_iterator_tag; // STL1-style iterator category
// Explicit opt-out of stl2's BidirectionalIterator concept:
using iterator_concept = std::forward_iterator_tag; // STL2-style iterator category
};
}
struct OutIter {
using difference_type = std::ptrdiff_t;
OutIter& operator=(int);
OutIter& operator*();
OutIter& operator++();
OutIter& operator++(int);
};
using namespace std;
template <ranges::InputIterator _I>
void test(_I) { printf("input\n"); }
template <ranges::ForwardIterator _I>
void test(_I) { printf("input\n"); }
template <ranges::BidirectionalIterator _I>
void test(_I) { printf("bidirectional\n"); }
template <ranges::Iterator _I>
void test2(_I) { printf("iterator\n"); }
template <ranges::InputIterator _I>
void test2(_I) { printf("input\n"); }
template <ranges::Iterator _I, ranges::Sentinel<_I> _S>
void test3(_I, _S) { printf("sentinel\n"); }
template <ranges::Iterator _I, ranges::SizedSentinel<_I> _S>
void test3(_I, _S) { printf("sized sentinel\n"); }
struct bool_iterator {
using value_type = bool;
struct reference {
operator bool() const { return true; }
reference& operator=(reference);
reference& operator=(bool);
};
using difference_type = std::ptrdiff_t;
reference operator*() const;
bool_iterator& operator++();
bool_iterator operator++(int);
bool operator==(bool_iterator) const;
bool operator!=(bool_iterator) const;
friend reference iter_move(bool_iterator i) { return *i; }
friend void iter_swap(bool_iterator, bool_iterator) { }
};
int main() {
static_assert(is_same_v<common_type_t<int, short&, int, char>, int>);
static_assert(is_same_v<common_reference_t<int &&, const int &, volatile int &>, const volatile int &>);
static_assert(is_same_v<common_reference_t<int &&, const int &, float &>, float>);
static_assert(is_same_v<iter_value_t<const int*>, int>);
static_assert(is_same_v<iter_difference_t<const int*>, ptrdiff_t>);
static_assert(is_same_v<iter_difference_t<int* const>, ptrdiff_t>);
static_assert(!_IsPrimary<iterator_traits, _X>);
static_assert(is_same_v<typename iterator_traits<_X>::value_type, int>);
static_assert(is_same_v<iter_value_t<_X>, int>);
static_assert(_IsPrimary<iterator_traits, _Y>);
static_assert(is_same_v<typename iterator_traits<_Y>::value_type, int>);
static_assert(is_same_v<iter_value_t<_Y>, int>);
// iterator_traits uses specializations of ranges::value_type:
static_assert(_IsPrimary<iterator_traits, _Z>);
static_assert(is_same_v<typename iterator_traits<_Z>::value_type, int>);
static_assert(is_same_v<iter_value_t<_Z>, int>);
static_assert(is_same_v<typename iterator_traits<_Z>::iterator_category,
std::bidirectional_iterator_tag>);
static_assert(ranges::InputIterator<WouldBeFwd>);
static_assert(!ranges::ForwardIterator<WouldBeFwd>);
static_assert(is_same_v<typename iterator_traits<WouldBeFwd>::iterator_category,
input_iterator_tag>);
static_assert(ranges::ForwardIterator<WouldBeBidi>);
static_assert(!ranges::BidirectionalIterator<WouldBeBidi>);
static_assert(is_same_v<typename iterator_traits<WouldBeBidi>::iterator_category,
input_iterator_tag>);
static_assert(ranges::Iterator<OutIter>);
static_assert(!ranges::InputIterator<OutIter>);
static_assert(is_same_v<typename iterator_traits<OutIter>::difference_type,
ptrdiff_t>);
static_assert(is_same_v<typename iterator_traits<OutIter>::iterator_category,
output_iterator_tag>);
static_assert(ranges::RandomAccessIterator<int volatile *>);
static_assert(ranges::ContiguousIterator<int volatile *>);
static_assert(ranges::ForwardIterator<bool_iterator>);
static_assert(is_same_v<typename iterator_traits<bool_iterator>::iterator_category,
std::input_iterator_tag>);
static_assert(_Cpp98InputIterator<int volatile*>);
static_assert(_Cpp98InputIterator<bool_iterator>);
// Test subsumption:
test(WouldBeFwd{});
test(WouldBeBidi{});
test(std::__nullptr_v<int>);
// Test subsumption:
test2(OutIter{});
test2(std::__nullptr_v<int>);
// Test subsumption:
test3(WouldBeFwd{}, WouldBeFwd{});
test3(std::__nullptr_v<int>, std::__nullptr_v<int>);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment