chromium/third_party/libc++/src/include/__iterator/iterator_traits.h

// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
#define _LIBCPP___ITERATOR_ITERATOR_TRAITS_H

#include <__concepts/arithmetic.h>
#include <__concepts/constructible.h>
#include <__concepts/convertible_to.h>
#include <__concepts/copyable.h>
#include <__concepts/equality_comparable.h>
#include <__concepts/same_as.h>
#include <__concepts/totally_ordered.h>
#include <__config>
#include <__fwd/pair.h>
#include <__iterator/incrementable_traits.h>
#include <__iterator/readable_traits.h>
#include <__type_traits/common_reference.h>
#include <__type_traits/conditional.h>
#include <__type_traits/disjunction.h>
#include <__type_traits/is_convertible.h>
#include <__type_traits/is_object.h>
#include <__type_traits/is_primary_template.h>
#include <__type_traits/is_reference.h>
#include <__type_traits/is_valid_expansion.h>
#include <__type_traits/remove_const.h>
#include <__type_traits/remove_cv.h>
#include <__type_traits/remove_cvref.h>
#include <__type_traits/void_t.h>
#include <__utility/declval.h>
#include <cstddef>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_BEGIN_NAMESPACE_STD

#if _LIBCPP_STD_VER >= 20

__with_reference;

__can_reference;

__dereferenceable;

// [iterator.traits]
iter_reference_t;

#endif // _LIBCPP_STD_VER >= 20

template <class _Iter>
struct _LIBCPP_TEMPLATE_VIS iterator_traits;

struct _LIBCPP_TEMPLATE_VIS input_iterator_tag { … };
struct _LIBCPP_TEMPLATE_VIS output_iterator_tag { … };
struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag { … };
struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag { … };
struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag { … };
#if _LIBCPP_STD_VER >= 20
struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag { … };
#endif

template <class _Iter>
struct __iter_traits_cache { … };
_ITER_TRAITS;

struct __iter_concept_concept_test { … };
struct __iter_concept_category_test { … };
struct __iter_concept_random_fallback { … };

template <class _Iter, class _Tester>
struct __test_iter_concept : _IsValidExpansion<_Tester::template _Apply, _Iter>, _Tester {};

template <class _Iter>
struct __iter_concept_cache { … };

_ITER_CONCEPT;

template <class _Tp>
struct __has_iterator_typedefs { … };

template <class _Tp>
struct __has_iterator_category { … };

template <class _Tp>
struct __has_iterator_concept { … };

#if _LIBCPP_STD_VER >= 20

// The `cpp17-*-iterator` exposition-only concepts have very similar names to the `Cpp17*Iterator` named requirements
// from `[iterator.cpp17]`. To avoid confusion between the two, the exposition-only concepts have been banished to
// a "detail" namespace indicating they have a niche use-case.
namespace __iterator_traits_detail {
__cpp17_iterator;

__cpp17_input_iterator;

__cpp17_forward_iterator;

__cpp17_bidirectional_iterator;

__cpp17_random_access_iterator;
} // namespace __iterator_traits_detail

__has_member_reference;

__has_member_pointer;

__has_member_iterator_category;

__specifies_members;

template <class>
struct __iterator_traits_member_pointer_or_void { … };

__iterator_traits_member_pointer_or_void<_Tp>;

__cpp17_iterator_missing_members;

__cpp17_input_iterator_missing_members;

// Otherwise, `pointer` names `void`.
template <class>
struct __iterator_traits_member_pointer_or_arrow_or_void { … };

// [iterator.traits]/3.2.1
// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type.
__iterator_traits_member_pointer_or_arrow_or_void<_Ip>;

// Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that
// type.
__iterator_traits_member_pointer_or_arrow_or_void<_Ip>;

// Otherwise, `reference` names `iter-reference-t<I>`.
template <class _Ip>
struct __iterator_traits_member_reference { … };

// [iterator.traits]/3.2.2
// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type.
__iterator_traits_member_reference<_Ip>;

// [iterator.traits]/3.2.3.4
// input_iterator_tag
template <class _Ip>
struct __deduce_iterator_category { … };

// [iterator.traits]/3.2.3.1
// `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise
__deduce_iterator_category<_Ip>;

// [iterator.traits]/3.2.3.2
// `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise
__deduce_iterator_category<_Ip>;

// [iterator.traits]/3.2.3.3
// `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise
__deduce_iterator_category<_Ip>;

template <class _Ip>
struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> { … };

// [iterator.traits]/3.2.3
// If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names
// that type.
__iterator_traits_iterator_category<_Ip>;

// otherwise, it names void.
template <class>
struct __iterator_traits_difference_type { … };

// If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then
// `difference_type` names that type;
__iterator_traits_difference_type<_Ip>;

// [iterator.traits]/3.4
// Otherwise, `iterator_traits<I>` has no members by any of the above names.
template <class>
struct __iterator_traits { … };

// [iterator.traits]/3.1
// If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and
// `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members:
__iterator_traits<_Ip>;

// [iterator.traits]/3.2
// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`,
// `iterator-traits<I>` has the following publicly accessible members:
__iterator_traits<_Ip>;

// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then
// `iterator_traits<I>` has the following publicly accessible members:
__iterator_traits<_Ip>;

template <class _Ip>
struct iterator_traits : __iterator_traits<_Ip> { … };

#else  // _LIBCPP_STD_VER >= 20

template <class _Iter, bool>
struct __iterator_traits {};

template <class _Iter, bool>
struct __iterator_traits_impl {};

template <class _Iter>
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 <class _Iter>
struct __iterator_traits<_Iter, true>
    : __iterator_traits_impl< _Iter,
                              is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
                                  is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value > {};

// iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
//    exists.  Else iterator_traits<Iterator> will be an empty class.  This is a
//    conforming extension which allows some programs to compile and behave as
//    the client expects instead of failing at compile time.

template <class _Iter>
struct _LIBCPP_TEMPLATE_VIS iterator_traits : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
  using __primary_template = iterator_traits;
};
#endif // _LIBCPP_STD_VER >= 20

iterator_traits<_Tp *>;

template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
struct __has_iterator_category_convertible_to : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up> { … };

__has_iterator_category_convertible_to<_Tp, _Up, false>;

template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
struct __has_iterator_concept_convertible_to : is_convertible<typename _Tp::iterator_concept, _Up> { … };

__has_iterator_concept_convertible_to<_Tp, _Up, false>;

__has_input_iterator_category;

__has_forward_iterator_category;

__has_bidirectional_iterator_category;

__has_random_access_iterator_category;

// __libcpp_is_contiguous_iterator determines if an iterator is known by
// libc++ to be contiguous, either because it advertises itself as such
// (in C++20) or because it is a pointer type or a known trivial wrapper
// around a (possibly fancy) pointer type, such as __wrap_iter<T*>.
// Such iterators receive special "contiguous" optimizations in
// std::copy and std::sort.
//
#if _LIBCPP_STD_VER >= 20
template <class _Tp>
struct __libcpp_is_contiguous_iterator
    : _Or< __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
           __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> > { … };
#else
template <class _Tp>
struct __libcpp_is_contiguous_iterator : false_type {};
#endif

// Any native pointer which is an iterator is also a contiguous iterator.
__libcpp_is_contiguous_iterator<_Up *>;

template <class _Iter>
class __wrap_iter;

__has_exactly_input_iterator_category;

__has_exactly_forward_iterator_category;

__has_exactly_bidirectional_iterator_category;

__iter_value_type;

__iter_key_type;

__iter_mapped_type;

__iter_to_alloc_type;

__iterator_category_type;

__iterator_pointer_type;

__iter_diff_t;

__iter_reference;

#if _LIBCPP_STD_VER >= 20

// [readable.traits]

// Let `RI` be `remove_cvref_t<I>`. The type `iter_value_t<I>` denotes
// `indirectly_readable_traits<RI>::value_type` if `iterator_traits<RI>` names a specialization
// generated from the primary template, and `iterator_traits<RI>::value_type` otherwise.
// This has to be in this file and not readable_traits.h to break the include cycle between the two.
iter_value_t;

#endif // _LIBCPP_STD_VER >= 20

_LIBCPP_END_NAMESPACE_STD

#endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H