Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- 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

//

//===----------------------------------------------------------------------===//

///

/// \file

/// This file contains some templates that are useful if you are working with

/// the STL at all.

///

/// No library is required when using these functions.

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_STLEXTRAS_H

#define LLVM_ADT_STLEXTRAS_H

#include "llvm/ADT/Hashing.h"

#include "llvm/ADT/STLForwardCompat.h"

#include "llvm/ADT/STLFunctionalExtras.h"

#include "llvm/ADT/identity.h"

#include "llvm/ADT/iterator.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/Config/abi-breaking.h"

#include "llvm/Support/ErrorHandling.h"

#include <algorithm>

#include <cassert>

#include <cstddef>

#include <cstdint>

#include <cstdlib>

#include <functional>

#include <initializer_list>

#include <iterator>

#include <limits>

#include <memory>

#include <optional>

#include <tuple>

#include <type_traits>

#include <utility>

#ifdef EXPENSIVE_CHECKS

#include <random> // for std::mt19937

#endif

namespace llvm {

// Only used by compiler if both template types are the same.  Useful when

// using SFINAE to test for the existence of member functions.

template <typename T, T> struct SameType;

namespace detail {

template <typename RangeT>

using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));

template <typename RangeT>

using ValueOfRange =

    std::remove_reference_t<decltype(*std::begin(std::declval<RangeT &>()))>;

} // end namespace detail

//===----------------------------------------------------------------------===//

//     Extra additions to <type_traits>

//===----------------------------------------------------------------------===//

template <typename T> struct make_const_ptr {

  using type = std::add_pointer_t<std::add_const_t<T>>;

};

template <typename T> struct make_const_ref {

  using type = std::add_lvalue_reference_t<std::add_const_t<T>>;

};

namespace detail {

template <class, template <class...> class Op, class... Args> struct detector {

  using value_t = std::false_type;

};

template <template <class...> class Op, class... Args>

struct detector<std::void_t<Op<Args...>>, Op, Args...> {

  using value_t = std::true_type;

};

} // end namespace detail

/// Detects if a given trait holds for some set of arguments 'Args'.

/// For example, the given trait could be used to detect if a given type

/// has a copy assignment operator:

///   template<class T>

///   using has_copy_assign_t = decltype(std::declval<T&>()

///                                                 = std::declval<const T&>());

///   bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value;

template <template <class...> class Op, class... Args>

using is_detected = typename detail::detector<void, Op, Args...>::value_t;

/// This class provides various trait information about a callable object.

///   * To access the number of arguments: Traits::num_args

///   * To access the type of an argument: Traits::arg_t<Index>

///   * To access the type of the result:  Traits::result_t

template <typename T, bool isClass = std::is_class<T>::value>

struct function_traits : public function_traits<decltype(&T::operator())> {};

/// Overload for class function types.

template <typename ClassType, typename ReturnType, typename... Args>

struct function_traits<ReturnType (ClassType::*)(Args...) const, false> {

  /// The number of arguments to this function.

  enum { num_args = sizeof...(Args) };

  /// The result type of this function.

  using result_t = ReturnType;

  /// The type of an argument to this function.

  template <size_t Index>

  using arg_t = std::tuple_element_t<Index, std::tuple<Args...>>;

};

/// Overload for class function types.

template <typename ClassType, typename ReturnType, typename... Args>

struct function_traits<ReturnType (ClassType::*)(Args...), false>

    : public function_traits<ReturnType (ClassType::*)(Args...) const> {};

/// Overload for non-class function types.

template <typename ReturnType, typename... Args>

struct function_traits<ReturnType (*)(Args...), false> {

  /// The number of arguments to this function.

  enum { num_args = sizeof...(Args) };

  /// The result type of this function.

  using result_t = ReturnType;

  /// The type of an argument to this function.

  template <size_t i>

  using arg_t = std::tuple_element_t<i, std::tuple<Args...>>;

};

template <typename ReturnType, typename... Args>

struct function_traits<ReturnType (*const)(Args...), false>

    : public function_traits<ReturnType (*)(Args...)> {};

/// Overload for non-class function type references.

template <typename ReturnType, typename... Args>

struct function_traits<ReturnType (&)(Args...), false>

    : public function_traits<ReturnType (*)(Args...)> {};

/// traits class for checking whether type T is one of any of the given

/// types in the variadic list.

template <typename T, typename... Ts>

using is_one_of = std::disjunction<std::is_same<T, Ts>...>;

/// traits class for checking whether type T is a base class for all

///  the given types in the variadic list.

template <typename T, typename... Ts>

using are_base_of = std::conjunction<std::is_base_of<T, Ts>...>;

namespace detail {

template <typename T, typename... Us> struct TypesAreDistinct;

template <typename T, typename... Us>

struct TypesAreDistinct

    : std::integral_constant<bool, !is_one_of<T, Us...>::value &&

                                       TypesAreDistinct<Us...>::value> {};

template <typename T> struct TypesAreDistinct<T> : std::true_type {};

} // namespace detail

/// Determine if all types in Ts are distinct.

///

/// Useful to statically assert when Ts is intended to describe a non-multi set

/// of types.

///

/// Expensive (currently quadratic in sizeof(Ts...)), and so should only be

/// asserted once per instantiation of a type which requires it.

template <typename... Ts> struct TypesAreDistinct;

template <> struct TypesAreDistinct<> : std::true_type {};

template <typename... Ts>

struct TypesAreDistinct

    : std::integral_constant<bool, detail::TypesAreDistinct<Ts...>::value> {};

/// Find the first index where a type appears in a list of types.

///

/// FirstIndexOfType<T, Us...>::value is the first index of T in Us.

///

/// Typically only meaningful when it is otherwise statically known that the

/// type pack has no duplicate types. This should be guaranteed explicitly with

/// static_assert(TypesAreDistinct<Us...>::value).

///

/// It is a compile-time error to instantiate when T is not present in Us, i.e.

/// if is_one_of<T, Us...>::value is false.

template <typename T, typename... Us> struct FirstIndexOfType;

template <typename T, typename U, typename... Us>

struct FirstIndexOfType<T, U, Us...>

    : std::integral_constant<size_t, 1 + FirstIndexOfType<T, Us...>::value> {};

template <typename T, typename... Us>

struct FirstIndexOfType<T, T, Us...> : std::integral_constant<size_t, 0> {};

/// Find the type at a given index in a list of types.

///

/// TypeAtIndex<I, Ts...> is the type at index I in Ts.

template <size_t I, typename... Ts>

using TypeAtIndex = std::tuple_element_t<I, std::tuple<Ts...>>;

/// Helper which adds two underlying types of enumeration type.

/// Implicit conversion to a common type is accepted.

template <typename EnumTy1, typename EnumTy2,

          typename UT1 = std::enable_if_t<std::is_enum<EnumTy1>::value,

                                          std::underlying_type_t<EnumTy1>>,

          typename UT2 = std::enable_if_t<std::is_enum<EnumTy2>::value,

                                          std::underlying_type_t<EnumTy2>>>

constexpr auto addEnumValues(EnumTy1 LHS, EnumTy2 RHS) {

  return static_cast<UT1>(LHS) + static_cast<UT2>(RHS);

}

//===----------------------------------------------------------------------===//

//     Extra additions to <iterator>

//===----------------------------------------------------------------------===//

namespace callable_detail {

/// Templated storage wrapper for a callable.

///

/// This class is consistently default constructible, copy / move

/// constructible / assignable.

///

/// Supported callable types:

///  - Function pointer

///  - Function reference

///  - Lambda

///  - Function object

template <typename T,

          bool = std::is_function_v<std::remove_pointer_t<remove_cvref_t<T>>>>

class Callable {

  using value_type = std::remove_reference_t<T>;

  using reference = value_type &;

  using const_reference = value_type const &;

  std::optional<value_type> Obj;

  static_assert(!std::is_pointer_v<value_type>,

                "Pointers to non-functions are not callable.");

public:

  Callable() = default;

  Callable(T const &O) : Obj(std::in_place, O) {}

  Callable(Callable const &Other) = default;

  Callable(Callable &&Other) = default;

  Callable &operator=(Callable const &Other) {

    Obj = std::nullopt;

    if (Other.Obj)

      Obj.emplace(*Other.Obj);

    return *this;

  }

  Callable &operator=(Callable &&Other) {

    Obj = std::nullopt;

    if (Other.Obj)

      Obj.emplace(std::move(*Other.Obj));

    return *this;

  }

  template <typename... Pn,

            std::enable_if_t<std::is_invocable_v<T, Pn...>, int> = 0>

  decltype(auto) operator()(Pn &&...Params) {

    return (*Obj)(std::forward<Pn>(Params)...);

  }

  template <typename... Pn,

            std::enable_if_t<std::is_invocable_v<T const, Pn...>, int> = 0>

  decltype(auto) operator()(Pn &&...Params) const {

    return (*Obj)(std::forward<Pn>(Params)...);

  }

  bool valid() const { return Obj != std::nullopt; }

  bool reset() { return Obj = std::nullopt; }

  operator reference() { return *Obj; }

  operator const_reference() const { return *Obj; }

};

// Function specialization.  No need to waste extra space wrapping with a

// std::optional.

template <typename T> class Callable<T, true> {

  static constexpr bool IsPtr = std::is_pointer_v<remove_cvref_t<T>>;

  using StorageT = std::conditional_t<IsPtr, T, std::remove_reference_t<T> *>;

  using CastT = std::conditional_t<IsPtr, T, T &>;

private:

  StorageT Func = nullptr;

private:

  template <typename In> static constexpr auto convertIn(In &&I) {

    if constexpr (IsPtr) {

      // Pointer... just echo it back.

      return I;

    } else {

      // Must be a function reference.  Return its address.

      return &I;

    }

  }

public:

  Callable() = default;

  // Construct from a function pointer or reference.

  //

  // Disable this constructor for references to 'Callable' so we don't violate

  // the rule of 0.

  template < // clang-format off

    typename FnPtrOrRef,

    std::enable_if_t<

      !std::is_same_v<remove_cvref_t<FnPtrOrRef>, Callable>, int

    > = 0

  > // clang-format on

  Callable(FnPtrOrRef &&F) : Func(convertIn(F)) {}

  template <typename... Pn,

            std::enable_if_t<std::is_invocable_v<T, Pn...>, int> = 0>

  decltype(auto) operator()(Pn &&...Params) const {

    return Func(std::forward<Pn>(Params)...);

  }

  bool valid() const { return Func != nullptr; }

  void reset() { Func = nullptr; }

  operator T const &() const {

    if constexpr (IsPtr) {

      // T is a pointer... just echo it back.

      return Func;

    } else {

      static_assert(std::is_reference_v<T>,

                    "Expected a reference to a function.");

      // T is a function reference... dereference the stored pointer.

      return *Func;

    }

  }

};

} // namespace callable_detail

namespace adl_detail {

using std::begin;

template <typename ContainerTy>

decltype(auto) adl_begin(ContainerTy &&container) {

  return begin(std::forward<ContainerTy>(container));

}

using std::end;

template <typename ContainerTy>

decltype(auto) adl_end(ContainerTy &&container) {

  return end(std::forward<ContainerTy>(container));

}

using std::swap;

template <typename T>

void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),

                                                       std::declval<T>()))) {

  swap(std::forward<T>(lhs), std::forward<T>(rhs));

}

} // end namespace adl_detail

template <typename ContainerTy>

decltype(auto) adl_begin(ContainerTy &&container) {

  return adl_detail::adl_begin(std::forward<ContainerTy>(container));

}

template <typename ContainerTy>

decltype(auto) adl_end(ContainerTy &&container) {

  return adl_detail::adl_end(std::forward<ContainerTy>(container));

}

template <typename T>

void adl_swap(T &&lhs, T &&rhs) noexcept(

    noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {

  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));

}

/// Returns true if the given container only contains a single element.

template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {

  auto B = std::begin(C), E = std::end(C);

  return B != E && std::next(B) == E;

}

/// Return a range covering \p RangeOrContainer with the first N elements

/// excluded.

template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N = 1) {

  return make_range(std::next(adl_begin(RangeOrContainer), N),

                    adl_end(RangeOrContainer));

}

/// Return a range covering \p RangeOrContainer with the last N elements

/// excluded.

template <typename T> auto drop_end(T &&RangeOrContainer, size_t N = 1) {

  return make_range(adl_begin(RangeOrContainer),

                    std::prev(adl_end(RangeOrContainer), N));

}

// mapped_iterator - This is a simple iterator adapter that causes a function to

// be applied whenever operator* is invoked on the iterator.

template <typename ItTy, typename FuncTy,

          typename ReferenceTy =

              decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>

class mapped_iterator

    : public iterator_adaptor_base<

          mapped_iterator<ItTy, FuncTy>, ItTy,

          typename std::iterator_traits<ItTy>::iterator_category,

          std::remove_reference_t<ReferenceTy>,

          typename std::iterator_traits<ItTy>::difference_type,

          std::remove_reference_t<ReferenceTy> *, ReferenceTy> {

public:

  mapped_iterator() = default;

  mapped_iterator(ItTy U, FuncTy F)

    : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}

  ItTy getCurrent() { return this->I; }

  const FuncTy &getFunction() const { return F; }

  ReferenceTy operator*() const { return F(*this->I); }

private:

  callable_detail::Callable<FuncTy> F{};

};

// map_iterator - Provide a convenient way to create mapped_iterators, just like

// make_pair is useful for creating pairs...

template <class ItTy, class FuncTy>

inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {

  return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));

}

template <class ContainerTy, class FuncTy>

auto map_range(ContainerTy &&C, FuncTy F) {

  return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));

}

/// A base type of mapped iterator, that is useful for building derived

/// iterators that do not need/want to store the map function (as in

/// mapped_iterator). These iterators must simply provide a `mapElement` method

/// that defines how to map a value of the iterator to the provided reference

/// type.

template <typename DerivedT, typename ItTy, typename ReferenceTy>

class mapped_iterator_base

    : public iterator_adaptor_base<

          DerivedT, ItTy,

          typename std::iterator_traits<ItTy>::iterator_category,

          std::remove_reference_t<ReferenceTy>,

          typename std::iterator_traits<ItTy>::difference_type,

          std::remove_reference_t<ReferenceTy> *, ReferenceTy> {

public:

  using BaseT = mapped_iterator_base;

  mapped_iterator_base(ItTy U)

      : mapped_iterator_base::iterator_adaptor_base(std::move(U)) {}

  ItTy getCurrent() { return this->I; }

  ReferenceTy operator*() const {

    return static_cast<const DerivedT &>(*this).mapElement(*this->I);

  }

};

/// Helper to determine if type T has a member called rbegin().

template <typename Ty> class has_rbegin_impl {

  using yes = char[1];

  using no = char[2];

  template <typename Inner>

  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);

  template <typename>

  static no& test(...);

public:

  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);

};

/// Metafunction to determine if T& or T has a member called rbegin().

template <typename Ty>

struct has_rbegin : has_rbegin_impl<std::remove_reference_t<Ty>> {};

// Returns an iterator_range over the given container which iterates in reverse.

template <typename ContainerTy> auto reverse(ContainerTy &&C) {

  if constexpr (has_rbegin<ContainerTy>::value)

    return make_range(C.rbegin(), C.rend());

  else

    return make_range(std::make_reverse_iterator(std::end(C)),

                      std::make_reverse_iterator(std::begin(C)));

}

/// An iterator adaptor that filters the elements of given inner iterators.

///

/// The predicate parameter should be a callable object that accepts the wrapped

/// iterator's reference type and returns a bool. When incrementing or

/// decrementing the iterator, it will call the predicate on each element and

/// skip any where it returns false.

///

/// \code

///   int A[] = { 1, 2, 3, 4 };

///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });

///   // R contains { 1, 3 }.

/// \endcode

///

/// Note: filter_iterator_base implements support for forward iteration.

/// filter_iterator_impl exists to provide support for bidirectional iteration,

/// conditional on whether the wrapped iterator supports it.

template <typename WrappedIteratorT, typename PredicateT, typename IterTag>

class filter_iterator_base

    : public iterator_adaptor_base<

          filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,

          WrappedIteratorT,

          std::common_type_t<IterTag,

                             typename std::iterator_traits<

                                 WrappedIteratorT>::iterator_category>> {

  using BaseT = typename filter_iterator_base::iterator_adaptor_base;

protected:

  WrappedIteratorT End;

  PredicateT Pred;

  void findNextValid() {

    while (this->I != End && !Pred(*this->I))

      BaseT::operator++();

  }

  filter_iterator_base() = default;

  // Construct the iterator. The begin iterator needs to know where the end

  // is, so that it can properly stop when it gets there. The end iterator only

  // needs the predicate to support bidirectional iteration.

  filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,

                       PredicateT Pred)

      : BaseT(Begin), End(End), Pred(Pred) {

    findNextValid();

  }

public:

  using BaseT::operator++;

  filter_iterator_base &operator++() {

    BaseT::operator++();

    findNextValid();

    return *this;

  }

  decltype(auto) operator*() const {

    assert(BaseT::wrapped() != End && "Cannot dereference end iterator!");

    return BaseT::operator*();

  }

  decltype(auto) operator->() const {

    assert(BaseT::wrapped() != End && "Cannot dereference end iterator!");

    return BaseT::operator->();

  }

};

/// Specialization of filter_iterator_base for forward iteration only.

template <typename WrappedIteratorT, typename PredicateT,

          typename IterTag = std::forward_iterator_tag>

class filter_iterator_impl

    : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {

public:

  filter_iterator_impl() = default;

  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,

                       PredicateT Pred)

      : filter_iterator_impl::filter_iterator_base(Begin, End, Pred) {}

};

/// Specialization of filter_iterator_base for bidirectional iteration.

template <typename WrappedIteratorT, typename PredicateT>

class filter_iterator_impl<WrappedIteratorT, PredicateT,

                           std::bidirectional_iterator_tag>

    : public filter_iterator_base<WrappedIteratorT, PredicateT,

                                  std::bidirectional_iterator_tag> {

  using BaseT = typename filter_iterator_impl::filter_iterator_base;

  void findPrevValid() {

    while (!this->Pred(*this->I))

      BaseT::operator--();

  }

public:

  using BaseT::operator--;

  filter_iterator_impl() = default;

  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,

                       PredicateT Pred)

      : BaseT(Begin, End, Pred) {}

  filter_iterator_impl &operator--() {

    BaseT::operator--();

    findPrevValid();

    return *this;

  }

};

namespace detail {

template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {

  using type = std::forward_iterator_tag;

};

template <> struct fwd_or_bidi_tag_impl<true> {

  using type = std::bidirectional_iterator_tag;

};

/// Helper which sets its type member to forward_iterator_tag if the category

/// of \p IterT does not derive from bidirectional_iterator_tag, and to

/// bidirectional_iterator_tag otherwise.

template <typename IterT> struct fwd_or_bidi_tag {

  using type = typename fwd_or_bidi_tag_impl<std::is_base_of<

      std::bidirectional_iterator_tag,

      typename std::iterator_traits<IterT>::iterator_category>::value>::type;

};

} // namespace detail

/// Defines filter_iterator to a suitable specialization of

/// filter_iterator_impl, based on the underlying iterator's category.

template <typename WrappedIteratorT, typename PredicateT>

using filter_iterator = filter_iterator_impl<

    WrappedIteratorT, PredicateT,

    typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;

/// Convenience function that takes a range of elements and a predicate,

/// and return a new filter_iterator range.

///

/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the

/// lifetime of that temporary is not kept by the returned range object, and the

/// temporary is going to be dropped on the floor after the make_iterator_range

/// full expression that contains this function call.

template <typename RangeT, typename PredicateT>

iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>

make_filter_range(RangeT &&Range, PredicateT Pred) {

  using FilterIteratorT =

      filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;

  return make_range(

      FilterIteratorT(std::begin(std::forward<RangeT>(Range)),

                      std::end(std::forward<RangeT>(Range)), Pred),

      FilterIteratorT(std::end(std::forward<RangeT>(Range)),

                      std::end(std::forward<RangeT>(Range)), Pred));

}

/// A pseudo-iterator adaptor that is designed to implement "early increment"

/// style loops.

///

/// This is *not a normal iterator* and should almost never be used directly. It

/// is intended primarily to be used with range based for loops and some range

/// algorithms.

///

/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but

/// somewhere between them. The constraints of these iterators are:

///

/// - On construction or after being incremented, it is comparable and

///   dereferencable. It is *not* incrementable.

/// - After being dereferenced, it is neither comparable nor dereferencable, it

///   is only incrementable.

///

/// This means you can only dereference the iterator once, and you can only

/// increment it once between dereferences.

template <typename WrappedIteratorT>

class early_inc_iterator_impl

    : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,

                                   WrappedIteratorT, std::input_iterator_tag> {

  using BaseT = typename early_inc_iterator_impl::iterator_adaptor_base;

  using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;

protected:

#if LLVM_ENABLE_ABI_BREAKING_CHECKS

  bool IsEarlyIncremented = false;

#endif

public:

  early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}

  using BaseT::operator*;

  decltype(*std::declval<WrappedIteratorT>()) operator*() {

#if LLVM_ENABLE_ABI_BREAKING_CHECKS

    assert(!IsEarlyIncremented && "Cannot dereference twice!");

    IsEarlyIncremented = true;

#endif

    return *(this->I)++;

  }

  using BaseT::operator++;

  early_inc_iterator_impl &operator++() {

#if LLVM_ENABLE_ABI_BREAKING_CHECKS

    assert(IsEarlyIncremented && "Cannot increment before dereferencing!");

    IsEarlyIncremented = false;

#endif

    return *this;

  }

  friend bool operator==(const early_inc_iterator_impl &LHS,

                         const early_inc_iterator_impl &RHS) {

#if LLVM_ENABLE_ABI_BREAKING_CHECKS

    assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!");

#endif

    return (const BaseT &)LHS == (const BaseT &)RHS;

  }

};

/// Make a range that does early increment to allow mutation of the underlying

/// range without disrupting iteration.

///

/// The underlying iterator will be incremented immediately after it is

/// dereferenced, allowing deletion of the current node or insertion of nodes to

/// not disrupt iteration provided they do not invalidate the *next* iterator --

/// the current iterator can be invalidated.

///

/// This requires a very exact pattern of use that is only really suitable to

/// range based for loops and other range algorithms that explicitly guarantee

/// to dereference exactly once each element, and to increment exactly once each

/// element.

template <typename RangeT>

iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>

make_early_inc_range(RangeT &&Range) {

  using EarlyIncIteratorT =

      early_inc_iterator_impl<detail::IterOfRange<RangeT>>;

  return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),

                    EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));

}

// Forward declarations required by zip_shortest/zip_equal/zip_first/zip_longest

template <typename R, typename UnaryPredicate>

bool all_of(R &&range, UnaryPredicate P);

template <typename R, typename UnaryPredicate>

bool any_of(R &&range, UnaryPredicate P);

template <typename T> bool all_equal(std::initializer_list<T> Values);

namespace detail {

using std::declval;

// We have to alias this since inlining the actual type at the usage site

// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.

template<typename... Iters> struct ZipTupleType {

  using type = std::tuple<decltype(*declval<Iters>())...>;

};

template <typename ZipType, typename... Iters>

using zip_traits = iterator_facade_base<

    ZipType,

    std::common_type_t<

        std::bidirectional_iterator_tag,