path: root/gcc/iterator-utils.h

// Iterator-related utilities.
// Copyright (C) 2002-2024 Free Software Foundation, Inc.
//
// This file is part of GCC.
//
// GCC 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.
//
// GCC 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.
//
// You should have received a copy of the GNU General Public License
// along with GCC; see the file COPYING3.  If not see
// <http://www.gnu.org/licenses/>.

#ifndef GCC_ITERATOR_UTILS_H
#define GCC_ITERATOR_UTILS_H 1

// A half-open [begin, end) range of iterators.
template<typename T>
struct iterator_range
{
public:
  using const_iterator = T;

  iterator_range () = default;
  iterator_range (const T &begin, const T &end)
    : m_begin (begin), m_end (end) {}

  T begin () const { return m_begin; }
  T end () const { return m_end; }

  explicit operator bool () const { return m_begin != m_end; }

private:
  T m_begin;
  T m_end;
};

// Provide an iterator like BaseIT, except that it yields values of type T,
// which is derived from the type that BaseIT normally yields.
//
// The class doesn't inherit from BaseIT for two reasons:
// - using inheritance would stop the class working with plain pointers
// - not using inheritance increases type-safety for writable iterators
//
// Constructing this class from a BaseIT involves an assertion that all
// contents really do have type T.  The constructor is therefore explicit.
template<typename T, typename BaseIT>
class derived_iterator
{
public:
  using value_type = T;

  derived_iterator () = default;

  template<typename... Ts>
  explicit derived_iterator (Ts... args)
    : m_base (std::forward<Ts> (args)...) {}

  derived_iterator &operator++ () { ++m_base; return *this; }
  derived_iterator operator++ (int);

  T operator* () const { return static_cast<T> (*m_base); }
  T *operator-> () const { return static_cast<T *> (m_base.operator-> ()); }

  bool operator== (const derived_iterator &other) const;
  bool operator!= (const derived_iterator &other) const;

protected:
  BaseIT m_base;
};

template<typename T, typename BaseIT>
inline derived_iterator<T, BaseIT>
derived_iterator<T, BaseIT>::operator++ (int)
{
  derived_iterator ret = *this;
  ++m_base;
  return ret;
}

template<typename T, typename BaseIT>
inline bool
derived_iterator<T, BaseIT>::operator== (const derived_iterator &other) const
{
  return m_base == other.m_base;
}

template<typename T, typename BaseIT>
inline bool
derived_iterator<T, BaseIT>::operator!= (const derived_iterator &other) const
{
  return m_base != other.m_base;
}

// Provide a constant view of a BaseCT in which every value is known to
// have type T, which is derived from the type that BaseCT normally presents.
//
// Constructing this class from a BaseCT involves an assertion that all
// contents really do have type T.  The constructor is therefore explicit.
template<typename T, typename BaseCT>
class const_derived_container : public BaseCT
{
  using base_const_iterator = typename BaseCT::const_iterator;

public:
  using value_type = T;
  using const_iterator = derived_iterator<T, base_const_iterator>;

  const_derived_container () = default;

  template<typename... Ts>
  explicit const_derived_container (Ts... args)
    : BaseCT (std::forward<Ts> (args)...) {}

  const_iterator begin () const { return const_iterator (BaseCT::begin ()); }
  const_iterator end () const { return const_iterator (BaseCT::end ()); }

  T front () const { return static_cast<T> (BaseCT::front ()); }
  T back () const { return static_cast<T> (BaseCT::back ()); }
  T operator[] (unsigned int i) const;
};

template<typename T, typename BaseCT>
inline T
const_derived_container<T, BaseCT>::operator[] (unsigned int i) const
{
  return static_cast<T> (BaseCT::operator[] (i));
}

// A base class for iterators whose contents consist of a StoredT and that
// when dereferenced yield those StoredT contents as a T.  Derived classes
// should implement at least operator++ or operator--.
template<typename T, typename StoredT = T>
class wrapper_iterator
{
public:
  using value_type = T;

  wrapper_iterator () = default;

  template<typename... Ts>
  wrapper_iterator (Ts... args) : m_contents (std::forward<Ts> (args)...) {}

  T operator* () const { return static_cast<T> (m_contents); }
  bool operator== (const wrapper_iterator &) const;
  bool operator!= (const wrapper_iterator &) const;

protected:
  StoredT m_contents;
};

template<typename T, typename StoredT>
inline bool
wrapper_iterator<T, StoredT>::operator== (const wrapper_iterator &other) const
{
  return m_contents == other.m_contents;
}

template<typename T, typename StoredT>
inline bool
wrapper_iterator<T, StoredT>::operator!= (const wrapper_iterator &other) const
{
  return m_contents != other.m_contents;
}

// A forward iterator for a linked list whose nodes are referenced using
// type T.  Given a node "T N", the next element is given by (N->*Next) ().
template<typename T, T *(T::*Next) () const>
class list_iterator : public wrapper_iterator<T *>
{
private:
  using parent = wrapper_iterator<T *>;

public:
  using parent::parent;
  list_iterator &operator++ ();
  list_iterator operator++ (int);
};

template<typename T, T *(T::*Next) () const>
inline list_iterator<T, Next> &
list_iterator<T, Next>::operator++ ()
{
  this->m_contents = (this->m_contents->*Next) ();
  return *this;
}

template<typename T, T *(T::*Next) () const>
inline list_iterator<T, Next>
list_iterator<T, Next>::operator++ (int)
{
  list_iterator ret = *this;
  this->m_contents = (this->m_contents->*Next) ();
  return ret;
}

// An iterator that pre-computes the next value if we haven't already got to the
// end.  This is useful in cases where a standard iterator would get invalidated
// (e.g. elements getting removed from a container) during the body of a loop.
template<typename T>
class safe_iterator
{
  T m_current;
  const T m_end;
  T m_next;

  T get_next ()
  {
    if (m_current != m_end)
      {
	// FIXME: we should use std::next here but that would mean having
	// #include <iterator> everywhere that iterator-utils.h is included.
	//
	// For now we just implement it directly.
	T iter = m_current;
	return ++iter;
      }
    return m_end;
  }

  void advance ()
  {
    m_current = m_next;
    if (m_next != m_end)
      ++m_next;
  }

public:
  bool operator== (const safe_iterator &other) const
  {
    return m_current == other.m_current;
  }

  bool operator!= (const safe_iterator &other) const
  {
    return m_current != other.m_current;
  }

  typename T::value_type operator*() const { return *m_current; }

  safe_iterator &operator++ ()
  {
    advance ();
    return *this;
  }

  safe_iterator operator++ (int)
  {
    auto ret = *this;
    advance ();
    return ret;
  }

  safe_iterator (T iter, T end)
    : m_current (iter), m_end (end), m_next (get_next ()) {}
};

// Convert a container RANGE into a container of safe_iterators.
template<typename Container>
inline
iterator_range<safe_iterator<typename Container::const_iterator>>
iterate_safely (Container range)
{
  return {
    { range.begin (), range.end () },
    { range.end (), range.end () }
  };
}

#endif