LCOV - code coverage report
Current view: top level - include/llvm/ADT - iterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 44 44 100.0 %
Date: 2017-09-14 15:23:50 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #ifndef LLVM_ADT_ITERATOR_H
      11             : #define LLVM_ADT_ITERATOR_H
      12             : 
      13             : #include "llvm/ADT/iterator_range.h"
      14             : #include <algorithm>
      15             : #include <cstddef>
      16             : #include <iterator>
      17             : #include <type_traits>
      18             : #include <utility>
      19             : 
      20             : namespace llvm {
      21             : 
      22             : /// \brief CRTP base class which implements the entire standard iterator facade
      23             : /// in terms of a minimal subset of the interface.
      24             : ///
      25             : /// Use this when it is reasonable to implement most of the iterator
      26             : /// functionality in terms of a core subset. If you need special behavior or
      27             : /// there are performance implications for this, you may want to override the
      28             : /// relevant members instead.
      29             : ///
      30             : /// Note, one abstraction that this does *not* provide is implementing
      31             : /// subtraction in terms of addition by negating the difference. Negation isn't
      32             : /// always information preserving, and I can see very reasonable iterator
      33             : /// designs where this doesn't work well. It doesn't really force much added
      34             : /// boilerplate anyways.
      35             : ///
      36             : /// Another abstraction that this doesn't provide is implementing increment in
      37             : /// terms of addition of one. These aren't equivalent for all iterator
      38             : /// categories, and respecting that adds a lot of complexity for little gain.
      39             : ///
      40             : /// Classes wishing to use `iterator_facade_base` should implement the following
      41             : /// methods:
      42             : ///
      43             : /// Forward Iterators:
      44             : ///   (All of the following methods)
      45             : ///   - DerivedT &operator=(const DerivedT &R);
      46             : ///   - bool operator==(const DerivedT &R) const;
      47             : ///   - const T &operator*() const;
      48             : ///   - T &operator*();
      49             : ///   - DerivedT &operator++();
      50             : ///
      51             : /// Bidirectional Iterators:
      52             : ///   (All methods of forward iterators, plus the following)
      53             : ///   - DerivedT &operator--();
      54             : ///
      55             : /// Random-access Iterators:
      56             : ///   (All methods of bidirectional iterators excluding the following)
      57             : ///   - DerivedT &operator++();
      58             : ///   - DerivedT &operator--();
      59             : ///   (and plus the following)
      60             : ///   - bool operator<(const DerivedT &RHS) const;
      61             : ///   - DifferenceTypeT operator-(const DerivedT &R) const;
      62             : ///   - DerivedT &operator+=(DifferenceTypeT N);
      63             : ///   - DerivedT &operator-=(DifferenceTypeT N);
      64             : ///
      65             : template <typename DerivedT, typename IteratorCategoryT, typename T,
      66             :           typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
      67             :           typename ReferenceT = T &>
      68             : class iterator_facade_base
      69             :     : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT,
      70             :                            ReferenceT> {
      71             : protected:
      72             :   enum {
      73             :     IsRandomAccess =
      74             :         std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value,
      75             :     IsBidirectional =
      76             :         std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value,
      77             :   };
      78             : 
      79             :   /// A proxy object for computing a reference via indirecting a copy of an
      80             :   /// iterator. This is used in APIs which need to produce a reference via
      81             :   /// indirection but for which the iterator object might be a temporary. The
      82             :   /// proxy preserves the iterator internally and exposes the indirected
      83             :   /// reference via a conversion operator.
      84             :   class ReferenceProxy {
      85             :     friend iterator_facade_base;
      86             : 
      87             :     DerivedT I;
      88             : 
      89          66 :     ReferenceProxy(DerivedT I) : I(std::move(I)) {}
      90             : 
      91             :   public:
      92         120 :     operator ReferenceT() const { return *I; }
      93             :   };
      94             : 
      95             : public:
      96             :   DerivedT operator+(DifferenceTypeT n) const {
      97             :     static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
      98             :                   "Must pass the derived type to this template!");
      99             :     static_assert(
     100             :         IsRandomAccess,
     101             :         "The '+' operator is only defined for random access iterators.");
     102      176977 :     DerivedT tmp = *static_cast<const DerivedT *>(this);
     103      176977 :     tmp += n;
     104             :     return tmp;
     105             :   }
     106             :   friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
     107             :     static_assert(
     108             :         IsRandomAccess,
     109             :         "The '+' operator is only defined for random access iterators.");
     110             :     return i + n;
     111             :   }
     112             :   DerivedT operator-(DifferenceTypeT n) const {
     113             :     static_assert(
     114             :         IsRandomAccess,
     115             :         "The '-' operator is only defined for random access iterators.");
     116       12471 :     DerivedT tmp = *static_cast<const DerivedT *>(this);
     117       12471 :     tmp -= n;
     118             :     return tmp;
     119             :   }
     120             : 
     121             :   DerivedT &operator++() {
     122             :     static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
     123             :                   "Must pass the derived type to this template!");
     124      128453 :     return static_cast<DerivedT *>(this)->operator+=(1);
     125             :   }
     126           6 :   DerivedT operator++(int) {
     127     7092387 :     DerivedT tmp = *static_cast<DerivedT *>(this);
     128    14168982 :     ++*static_cast<DerivedT *>(this);
     129           6 :     return tmp;
     130             :   }
     131             :   DerivedT &operator--() {
     132             :     static_assert(
     133             :         IsBidirectional,
     134             :         "The decrement operator is only defined for bidirectional iterators.");
     135           5 :     return static_cast<DerivedT *>(this)->operator-=(1);
     136             :   }
     137             :   DerivedT operator--(int) {
     138             :     static_assert(
     139             :         IsBidirectional,
     140             :         "The decrement operator is only defined for bidirectional iterators.");
     141             :     DerivedT tmp = *static_cast<DerivedT *>(this);
     142             :     --*static_cast<DerivedT *>(this);
     143             :     return tmp;
     144             :   }
     145             : 
     146          18 :   bool operator!=(const DerivedT &RHS) const {
     147  1502120442 :     return !static_cast<const DerivedT *>(this)->operator==(RHS);
     148             :   }
     149             : 
     150             :   bool operator>(const DerivedT &RHS) const {
     151             :     static_assert(
     152             :         IsRandomAccess,
     153             :         "Relational operators are only defined for random access iterators.");
     154          54 :     return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
     155          18 :            !static_cast<const DerivedT *>(this)->operator==(RHS);
     156             :   }
     157             :   bool operator<=(const DerivedT &RHS) const {
     158             :     static_assert(
     159             :         IsRandomAccess,
     160             :         "Relational operators are only defined for random access iterators.");
     161           4 :     return !static_cast<const DerivedT *>(this)->operator>(RHS);
     162             :   }
     163             :   bool operator>=(const DerivedT &RHS) const {
     164             :     static_assert(
     165             :         IsRandomAccess,
     166             :         "Relational operators are only defined for random access iterators.");
     167          20 :     return !static_cast<const DerivedT *>(this)->operator<(RHS);
     168             :   }
     169             : 
     170    55365802 :   PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); }
     171             :   PointerT operator->() const {
     172     9099179 :     return &static_cast<const DerivedT *>(this)->operator*();
     173             :   }
     174             :   ReferenceProxy operator[](DifferenceTypeT n) {
     175             :     static_assert(IsRandomAccess,
     176             :                   "Subscripting is only defined for random access iterators.");
     177         124 :     return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n));
     178             :   }
     179             :   ReferenceProxy operator[](DifferenceTypeT n) const {
     180             :     static_assert(IsRandomAccess,
     181             :                   "Subscripting is only defined for random access iterators.");
     182             :     return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n));
     183             :   }
     184             : };
     185             : 
     186             : /// \brief CRTP base class for adapting an iterator to a different type.
     187             : ///
     188             : /// This class can be used through CRTP to adapt one iterator into another.
     189             : /// Typically this is done through providing in the derived class a custom \c
     190             : /// operator* implementation. Other methods can be overridden as well.
     191             : template <
     192             :     typename DerivedT, typename WrappedIteratorT,
     193             :     typename IteratorCategoryT =
     194             :         typename std::iterator_traits<WrappedIteratorT>::iterator_category,
     195             :     typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
     196             :     typename DifferenceTypeT =
     197             :         typename std::iterator_traits<WrappedIteratorT>::difference_type,
     198             :     typename PointerT = typename std::conditional<
     199             :         std::is_same<T, typename std::iterator_traits<
     200             :                             WrappedIteratorT>::value_type>::value,
     201             :         typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type,
     202             :     typename ReferenceT = typename std::conditional<
     203             :         std::is_same<T, typename std::iterator_traits<
     204             :                             WrappedIteratorT>::value_type>::value,
     205             :         typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type,
     206             :     // Don't provide these, they are mostly to act as aliases below.
     207             :     typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>>
     208     9762998 : class iterator_adaptor_base
     209             :     : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
     210             :                                   DifferenceTypeT, PointerT, ReferenceT> {
     211             :   using BaseT = typename iterator_adaptor_base::iterator_facade_base;
     212             : 
     213             : protected:
     214             :   WrappedIteratorT I;
     215             : 
     216     8250603 :   iterator_adaptor_base() = default;
     217             : 
     218   831884087 :   explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {
     219             :     static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
     220             :                   "Must pass the derived type to this template!");
     221             :   }
     222             : 
     223             :   const WrappedIteratorT &wrapped() const { return I; }
     224             : 
     225             : public:
     226             :   using difference_type = DifferenceTypeT;
     227             : 
     228             :   DerivedT &operator+=(difference_type n) {
     229             :     static_assert(
     230             :         BaseT::IsRandomAccess,
     231             :         "The '+=' operator is only defined for random access iterators.");
     232      215553 :     I += n;
     233             :     return *static_cast<DerivedT *>(this);
     234             :   }
     235             :   DerivedT &operator-=(difference_type n) {
     236             :     static_assert(
     237             :         BaseT::IsRandomAccess,
     238             :         "The '-=' operator is only defined for random access iterators.");
     239       12470 :     I -= n;
     240             :     return *static_cast<DerivedT *>(this);
     241             :   }
     242             :   using BaseT::operator-;
     243             :   difference_type operator-(const DerivedT &RHS) const {
     244             :     static_assert(
     245             :         BaseT::IsRandomAccess,
     246             :         "The '-' operator is only defined for random access iterators.");
     247     4196177 :     return I - RHS.I;
     248             :   }
     249             : 
     250             :   // We have to explicitly provide ++ and -- rather than letting the facade
     251             :   // forward to += because WrappedIteratorT might not support +=.
     252             :   using BaseT::operator++;
     253             :   DerivedT &operator++() {
     254   957808276 :     ++I;
     255             :     return *static_cast<DerivedT *>(this);
     256             :   }
     257             :   using BaseT::operator--;
     258             :   DerivedT &operator--() {
     259             :     static_assert(
     260             :         BaseT::IsBidirectional,
     261             :         "The decrement operator is only defined for bidirectional iterators.");
     262     1020898 :     --I;
     263             :     return *static_cast<DerivedT *>(this);
     264             :   }
     265             : 
     266    64235822 :   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
     267             :   bool operator<(const DerivedT &RHS) const {
     268             :     static_assert(
     269             :         BaseT::IsRandomAccess,
     270             :         "Relational operators are only defined for random access iterators.");
     271          34 :     return I < RHS.I;
     272             :   }
     273             : 
     274      127921 :   ReferenceT operator*() const { return *I; }
     275             : };
     276             : 
     277             : /// \brief An iterator type that allows iterating over the pointees via some
     278             : /// other iterator.
     279             : ///
     280             : /// The typical usage of this is to expose a type that iterates over Ts, but
     281             : /// which is implemented with some iterator over T*s:
     282             : ///
     283             : /// \code
     284             : ///   using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
     285             : /// \endcode
     286             : template <typename WrappedIteratorT,
     287             :           typename T = typename std::remove_reference<
     288             :               decltype(**std::declval<WrappedIteratorT>())>::type>
     289       32112 : struct pointee_iterator
     290             :     : iterator_adaptor_base<
     291             :           pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
     292             :           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
     293             :           T> {
     294             :   pointee_iterator() = default;
     295             :   template <typename U>
     296      308962 :   pointee_iterator(U &&u)
     297     1470990 :       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
     298             : 
     299     6039914 :   T &operator*() const { return **this->I; }
     300             : };
     301             : 
     302             : template <typename RangeT, typename WrappedIteratorT =
     303             :                                decltype(std::begin(std::declval<RangeT>()))>
     304             : iterator_range<pointee_iterator<WrappedIteratorT>>
     305             : make_pointee_range(RangeT &&Range) {
     306             :   using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
     307           3 :   return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
     308           3 :                     PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
     309             : }
     310             : 
     311             : template <typename WrappedIteratorT,
     312             :           typename T = decltype(&*std::declval<WrappedIteratorT>())>
     313             : class pointer_iterator
     314             :     : public iterator_adaptor_base<pointer_iterator<WrappedIteratorT>,
     315             :                                    WrappedIteratorT, T> {
     316             :   mutable T Ptr;
     317             : 
     318             : public:
     319             :   pointer_iterator() = default;
     320             : 
     321         185 :   explicit pointer_iterator(WrappedIteratorT u)
     322     2069546 :       : pointer_iterator::iterator_adaptor_base(std::move(u)) {}
     323             : 
     324     2354198 :   T &operator*() { return Ptr = &*this->I; }
     325           5 :   const T &operator*() const { return Ptr = &*this->I; }
     326             : };
     327             : 
     328             : template <typename RangeT, typename WrappedIteratorT =
     329             :                                decltype(std::begin(std::declval<RangeT>()))>
     330             : iterator_range<pointer_iterator<WrappedIteratorT>>
     331             : make_pointer_range(RangeT &&Range) {
     332             :   using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
     333           3 :   return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
     334           1 :                     PointerIteratorT(std::end(std::forward<RangeT>(Range))));
     335             : }
     336             : 
     337             : } // end namespace llvm
     338             : 
     339             : #endif // LLVM_ADT_ITERATOR_H

Generated by: LCOV version 1.13