// Debugging support implementation -*- C++ -*-

// Copyright (C) 2003-2020 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file debug/helper_functions.h
 *  This file is a GNU debug extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H
#define _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H 1

#include <bits/move.h>				// for __addressof
#include <bits/stl_iterator_base_types.h>	// for iterator_traits,
						// categories and _Iter_base
#include <bits/cpp_type_traits.h>		// for __is_integer

#include <bits/stl_pair.h>			// for pair

namespace __gnu_debug
{
  template<typename _Iterator, typename _Sequence, typename _Category>
    class _Safe_iterator;

#if __cplusplus >= 201103L
  template<typename _Iterator, typename _Sequence>
    class _Safe_local_iterator;
#endif

  /** The precision to which we can calculate the distance between
   *  two iterators.
   */
  enum _Distance_precision
    {
      __dp_none,		// Not even an iterator type
      __dp_equality,		//< Can compare iterator equality, only
      __dp_sign,		//< Can determine equality and ordering
      __dp_sign_max_size,	//< __dp_sign and gives max range size
      __dp_exact		//< Can determine distance precisely
    };

  template<typename _Iterator,
	   typename = typename std::__is_integer<_Iterator>::__type>
    struct _Distance_traits
    {
    private:
      typedef
	typename std::iterator_traits<_Iterator>::difference_type _ItDiffType;

      template<typename _DiffType,
	       typename = typename std::__is_void<_DiffType>::__type>
	struct _DiffTraits
	{ typedef _DiffType __type; };

      template<typename _DiffType>
	struct _DiffTraits<_DiffType, std::__true_type>
	{ typedef std::ptrdiff_t __type; };

      typedef typename _DiffTraits<_ItDiffType>::__type _DiffType;

    public:
      typedef std::pair<_DiffType, _Distance_precision> __type;
    };

  template<typename _Integral>
    struct _Distance_traits<_Integral, std::__true_type>
    { typedef std::pair<std::ptrdiff_t, _Distance_precision> __type; };

  /** Determine the distance between two iterators with some known
   *	precision.
  */
  template<typename _Iterator>
    _GLIBCXX_CONSTEXPR
    inline typename _Distance_traits<_Iterator>::__type
    __get_distance(_Iterator __lhs, _Iterator __rhs,
		   std::random_access_iterator_tag)
    { return std::make_pair(__rhs - __lhs, __dp_exact); }

  template<typename _Iterator>
    _GLIBCXX14_CONSTEXPR
    inline typename _Distance_traits<_Iterator>::__type
    __get_distance(_Iterator __lhs, _Iterator __rhs,
		   std::input_iterator_tag)
    {
      if (__lhs == __rhs)
	return std::make_pair(0, __dp_exact);

      return std::make_pair(1, __dp_equality);
    }

  template<typename _Iterator>
    _GLIBCXX_CONSTEXPR
    inline typename _Distance_traits<_Iterator>::__type
    __get_distance(_Iterator __lhs, _Iterator __rhs)
    { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); }

  // An arbitrary iterator pointer is not singular.
  inline bool
  __check_singular_aux(const void*) { return false; }

  // We may have an iterator that derives from _Safe_iterator_base but isn't
  // a _Safe_iterator.
  template<typename _Iterator>
    inline bool
    __check_singular(_Iterator const& __x)
    { return __check_singular_aux(std::__addressof(__x)); }

  /** Non-NULL pointers are nonsingular. */
  template<typename _Tp>
    inline bool
    __check_singular(_Tp* const& __ptr)
    { return __ptr == 0; }

  /** We say that integral types for a valid range, and defer to other
   *  routines to realize what to do with integral types instead of
   *  iterators.
  */
  template<typename _Integral>
    _GLIBCXX_CONSTEXPR
    inline bool
    __valid_range_aux(_Integral, _Integral, std::__true_type)
    { return true; }

  template<typename _Integral>
    _GLIBCXX20_CONSTEXPR
    inline bool
    __valid_range_aux(_Integral, _Integral,
		      typename _Distance_traits<_Integral>::__type& __dist,
		      std::__true_type)
    {
      __dist = std::make_pair(0, __dp_none);
      return true;
    }

  template<typename _InputIterator>
    _GLIBCXX_CONSTEXPR
    inline bool
    __valid_range_aux(_InputIterator __first, _InputIterator __last,
		      std::input_iterator_tag)
    {
      return __first == __last
	|| (!__check_singular(__first) && !__check_singular(__last));
    }

  template<typename _InputIterator>
    _GLIBCXX_CONSTEXPR
    inline bool
    __valid_range_aux(_InputIterator __first, _InputIterator __last,
		      std::random_access_iterator_tag)
    {
      return
	__valid_range_aux(__first, __last, std::input_iterator_tag())
	&& __first <= __last;
    }

  /** We have iterators, so figure out what kind of iterators they are
   *  to see if we can check the range ahead of time.
  */
  template<typename _InputIterator>
    _GLIBCXX_CONSTEXPR
    inline bool
    __valid_range_aux(_InputIterator __first, _InputIterator __last,
		      std::__false_type)
    {
      return __valid_range_aux(__first, __last,
			       std::__iterator_category(__first));
    }

  template<typename _InputIterator>
    _GLIBCXX20_CONSTEXPR
    inline bool
    __valid_range_aux(_InputIterator __first, _InputIterator __last,
		      typename _Distance_traits<_InputIterator>::__type& __dist,
		      std::__false_type)
    {
      if (!__valid_range_aux(__first, __last, std::input_iterator_tag()))
	return false;

      __dist = __get_distance(__first, __last);
      switch (__dist.second)
	{
	case __dp_none:
	  break;
	case __dp_equality:
	  if (__dist.first == 0)
	    return true;
	  break;
	case __dp_sign:
	case __dp_sign_max_size:
	case __dp_exact:
	  return __dist.first >= 0;
	}

      // Can't tell so assume it is fine.
      return true;
    }

  /** Don't know what these iterators are, or if they are even
   *  iterators (we may get an integral type for InputIterator), so
   *  see if they are integral and pass them on to the next phase
   *  otherwise.
  */
  template<typename _InputIterator>
    _GLIBCXX20_CONSTEXPR
    inline bool
    __valid_range(_InputIterator __first, _InputIterator __last,
		  typename _Distance_traits<_InputIterator>::__type& __dist)
    {
#ifdef __cpp_lib_is_constant_evaluated
      if (std::is_constant_evaluated())
	// Detected by the compiler directly.
	return true;
#endif
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      return __valid_range_aux(__first, __last, __dist, _Integral());
    }

  template<typename _Iterator, typename _Sequence, typename _Category>
    bool
    __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
		  const _Safe_iterator<_Iterator, _Sequence, _Category>&,
		  typename _Distance_traits<_Iterator>::__type&);

#if __cplusplus >= 201103L
  template<typename _Iterator,typename _Sequence>
    bool
    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
		  const _Safe_local_iterator<_Iterator, _Sequence>&,
		  typename _Distance_traits<_Iterator>::__type&);
#endif

  template<typename _InputIterator>
    _GLIBCXX14_CONSTEXPR
    inline bool
    __valid_range(_InputIterator __first, _InputIterator __last)
    {
#ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
      if (__builtin_is_constant_evaluated())
	// Detected by the compiler directly.
	return true;
#endif
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      return __valid_range_aux(__first, __last, _Integral());
    }

  template<typename _Iterator, typename _Sequence, typename _Category>
    bool
    __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
		  const _Safe_iterator<_Iterator, _Sequence, _Category>&);

#if __cplusplus >= 201103L
  template<typename _Iterator, typename _Sequence>
    bool
    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
		  const _Safe_local_iterator<_Iterator, _Sequence>&);
#endif

  // Fallback method, always ok.
  template<typename _InputIterator, typename _Size>
    _GLIBCXX_CONSTEXPR
    inline bool
    __can_advance(_InputIterator, _Size)
    { return true; }

  template<typename _Iterator, typename _Sequence, typename _Category,
	   typename _Size>
    bool
    __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
		  _Size);

  template<typename _InputIterator, typename _Diff>
    _GLIBCXX_CONSTEXPR
    inline bool
    __can_advance(_InputIterator, const std::pair<_Diff, _Distance_precision>&, int)
    { return true; }

  template<typename _Iterator, typename _Sequence, typename _Category,
	   typename _Diff>
    bool
    __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
		  const std::pair<_Diff, _Distance_precision>&, int);

  /** Helper function to extract base iterator of random access safe iterator
   *  in order to reduce performance impact of debug mode.  Limited to random
   *  access iterator because it is the only category for which it is possible
   *  to check for correct iterators order in the __valid_range function
   *  thanks to the < operator.
   */
  template<typename _Iterator>
    _GLIBCXX_CONSTEXPR
    inline _Iterator
    __base(_Iterator __it)
    { return __it; }

#if __cplusplus < 201103L
  template<typename _Iterator>
    struct _Unsafe_type
    { typedef _Iterator _Type; };
#endif

  /* Remove debug mode safe iterator layer, if any. */
  template<typename _Iterator>
    inline _Iterator
    __unsafe(_Iterator __it)
    { return __it; }
}

#endif