[05/23] Add more iterator utilities

[Richard Sandiford <richard.sandiford@arm.com>]

This patch adds some more iterator helper classes.  They really fall
into two groups, but there didn't seem much value in separating them:

- A later patch has a class hierarchy of the form:

     Base
      +- Derived1
      +- Derived2

  A class wants to store an array A1 of Derived1 pointers and an
  array A2 of Derived2 pointers.  However, for compactness reasons,
  it was convenient to have a single array of Base pointers,
  with A1 and A2 being slices of this array.  This reduces the
  overhead from two pointers and two ints (3 LP64 words) to one
  pointer and two ints (2 LP64 words).

  But consumers of the class shouldn't be aware of this: they should
  see A1 as containing Derived1 pointers rather than Base pointers
  and A2 as containing Derived2 pointers rather than Base pointers.
  This patch adds derived_iterator and const_derived_container
  classes to support this use case.

- A later patch also adds various linked lists.  This patch adds
  wrapper_iterator and list_iterator classes to make it easier
  to create iterators for these linked lists.  For example:

    // Iterators for lists of definitions.
    using def_iterator = list_iterator<def_info, &def_info::next_def>;
    using reverse_def_iterator
      = list_iterator<def_info, &def_info::prev_def>;

  This in turn makes it possible to use range-based for loops
  on the lists.

The patch just adds the things that the later patches need; it doesn't
try to make the classes as functionally complete as possible.  I think
we should add extra functionality when needed rather than ahead of time.

gcc/
	* iterator-utils.h (derived_iterator): New class.
	(const_derived_container, wrapper_iterator): Likewise.
	(list_iterator): Likewise.
---
 gcc/iterator-utils.h | 159 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 159 insertions(+)

diff --git a/gcc/iterator-utils.h b/gcc/iterator-utils.h
index 0c95862c7ca..22cc1a545ef 100644
--- a/gcc/iterator-utils.h
+++ b/gcc/iterator-utils.h
@@ -41,4 +41,163 @@ private:
   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;
+}
+
 #endif
-- 
2.17.1