LCOV - code coverage report
Current view: top level - include/llvm/ADT - iterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 128 477 26.8 %
Date: 2018-10-14 09:39:32 Functions: 2 735 0.3 %
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             : /// 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 = std::is_base_of<std::random_access_iterator_tag,
      74             :                                      IteratorCategoryT>::value,
      75             :     IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag,
      76             :                                       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             :     ReferenceProxy(DerivedT I) : I(std::move(I)) {}
      90             : 
      91             :   public:
      92           6 :     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          26 :     DerivedT tmp = *static_cast<const DerivedT *>(this);
     103             :     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          10 :     DerivedT tmp = *static_cast<const DerivedT *>(this);
     117             :     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       15500 :     return static_cast<DerivedT *>(this)->operator+=(1);
     125             :   }
     126           0 :   DerivedT operator++(int) {
     127    29219966 :     DerivedT tmp = *static_cast<DerivedT *>(this);
     128        1022 :     ++*static_cast<DerivedT *>(this);
     129           0 :     return tmp;
     130             :   }
     131           0 :   DerivedT &operator--() {
     132           0 :     static_assert(
     133             :         IsBidirectional,
     134           0 :         "The decrement operator is only defined for bidirectional iterators.");
     135           0 :     return static_cast<DerivedT *>(this)->operator-=(1);
     136           0 :   }
     137           0 :   DerivedT operator--(int) {
     138           0 :     static_assert(
     139           0 :         IsBidirectional,
     140             :         "The decrement operator is only defined for bidirectional iterators.");
     141           0 :     DerivedT tmp = *static_cast<DerivedT *>(this);
     142           0 :     --*static_cast<DerivedT *>(this);
     143             :     return tmp;
     144           0 :   }
     145             : 
     146         909 :   bool operator!=(const DerivedT &RHS) const {
     147  1008151652 :     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             :     return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
     155             :            !static_cast<const DerivedT *>(this)->operator==(RHS);
     156             :   }
     157          10 :   bool operator<=(const DerivedT &RHS) const {
     158             :     static_assert(
     159             :         IsRandomAccess,
     160             :         "Relational operators are only defined for random access iterators.");
     161             :     return !static_cast<const DerivedT *>(this)->operator>(RHS);
     162          48 :   }
     163             :   bool operator>=(const DerivedT &RHS) const {
     164          20 :     static_assert(
     165             :         IsRandomAccess,
     166             :         "Relational operators are only defined for random access iterators.");
     167             :     return !static_cast<const DerivedT *>(this)->operator<(RHS);
     168             :   }
     169             : 
     170    56988840 :   PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); }
     171             :   PointerT operator->() const {
     172         362 :     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           8 :     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             : /// 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             : 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             :   iterator_adaptor_base() = default;
     217             : 
     218     1846414 :   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           0 :   DerivedT &operator+=(difference_type n) {
     229             :     static_assert(
     230             :         BaseT::IsRandomAccess,
     231             :         "The '+=' operator is only defined for random access iterators.");
     232     4008417 :     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           8 :     I -= n;
     240             :     return *static_cast<DerivedT *>(this);
     241             :   }
     242          38 :   using BaseT::operator-;
     243           0 :   difference_type operator-(const DerivedT &RHS) const {
     244             :     static_assert(
     245             :         BaseT::IsRandomAccess,
     246             :         "The '-' operator is only defined for random access iterators.");
     247    67164232 :     return I - RHS.I;
     248             :   }
     249           8 : 
     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           0 :   DerivedT &operator++() {
     254  1408738429 :     ++I;
     255           0 :     return *static_cast<DerivedT *>(this);
     256             :   }
     257          10 :   using BaseT::operator--;
     258           0 :   DerivedT &operator--() {
     259           0 :     static_assert(
     260             :         BaseT::IsBidirectional,
     261           0 :         "The decrement operator is only defined for bidirectional iterators.");
     262        1509 :     --I;
     263           0 :     return *static_cast<DerivedT *>(this);
     264             :   }
     265           0 : 
     266   786478653 :   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
     267           0 :   bool operator<(const DerivedT &RHS) const {
     268             :     static_assert(
     269         105 :         BaseT::IsRandomAccess,
     270             :         "Relational operators are only defined for random access iterators.");
     271           0 :     return I < RHS.I;
     272     1656308 :   }
     273           0 : 
     274      782759 :   ReferenceT operator*() const { return *I; }
     275             : };
     276          56 : 
     277           1 : /// An iterator type that allows iterating over the pointees via some
     278          79 : /// other iterator.
     279           0 : ///
     280             : /// The typical usage of this is to expose a type that iterates over Ts, but
     281           0 : /// which is implemented with some iterator over T*s:
     282             : ///
     283           0 : /// \code
     284     3961827 : ///   using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
     285           0 : /// \endcode
     286           0 : template <typename WrappedIteratorT,
     287             :           typename T = typename std::remove_reference<
     288           0 :               decltype(**std::declval<WrappedIteratorT>())>::type>
     289           0 : struct pointee_iterator
     290        1004 :     : iterator_adaptor_base<
     291           0 :           pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
     292             :           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
     293           2 :           T> {
     294             :   pointee_iterator() = default;
     295           0 :   template <typename U>
     296         872 :   pointee_iterator(U &&u)
     297           3 :       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
     298             : 
     299    20000050 :   T &operator*() const { return **this->I; }
     300             : };
     301           0 : 
     302         885 : template <typename RangeT, typename WrappedIteratorT =
     303           0 :                                decltype(std::begin(std::declval<RangeT>()))>
     304             : iterator_range<pointee_iterator<WrappedIteratorT>>
     305           0 : make_pointee_range(RangeT &&Range) {
     306             :   using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
     307           0 :   return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
     308        3095 :                     PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
     309         622 : }
     310             : 
     311        4383 : template <typename WrappedIteratorT,
     312           8 :           typename T = decltype(&*std::declval<WrappedIteratorT>())>
     313           0 : class pointer_iterator
     314       14380 :     : public iterator_adaptor_base<pointer_iterator<WrappedIteratorT, T>,
     315        1634 :                                    WrappedIteratorT, T> {
     316             :   mutable T Ptr;
     317        3691 : 
     318             : public:
     319           0 :   pointer_iterator() = default;
     320       14698 : 
     321         127 :   explicit pointer_iterator(WrappedIteratorT u)
     322             :       : pointer_iterator::iterator_adaptor_base(std::move(u)) {}
     323          79 : 
     324           1 :   T &operator*() { return Ptr = &*this->I; }
     325           0 :   const T &operator*() const { return Ptr = &*this->I; }
     326         261 : };
     327         128 : 
     328             : template <typename RangeT, typename WrappedIteratorT =
     329         355 :                                decltype(std::begin(std::declval<RangeT>()))>
     330          10 : iterator_range<pointer_iterator<WrappedIteratorT>>
     331          34 : make_pointer_range(RangeT &&Range) {
     332        1004 :   using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
     333         516 :   return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
     334             :                     PointerIteratorT(std::end(std::forward<RangeT>(Range))));
     335        1004 : }
     336             : 
     337           0 : // Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
     338         807 : // to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
     339         388 : template <typename ItType, typename NodeRef, typename DataRef>
     340             : class WrappedPairNodeDataIterator
     341         796 :     : public iterator_adaptor_base<
     342             :           WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
     343           0 :           typename std::iterator_traits<ItType>::iterator_category, NodeRef,
     344         780 :           std::ptrdiff_t, NodeRef *, NodeRef &> {
     345         390 :   using BaseT = iterator_adaptor_base<
     346             :       WrappedPairNodeDataIterator, ItType,
     347         879 :       typename std::iterator_traits<ItType>::iterator_category, NodeRef,
     348             :       std::ptrdiff_t, NodeRef *, NodeRef &>;
     349           0 : 
     350        1682 :   const DataRef DR;
     351         840 :   mutable NodeRef NR;
     352             : 
     353        1836 : public:
     354             :   WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
     355           3 :       : BaseT(Begin), DR(DR) {
     356       10862 :     NR.first = DR;
     357        5428 :   }
     358           4 : 
     359       10950 :   NodeRef &operator*() const {
     360        9511 :     NR.second = *this->I;
     361        9511 :     return NR;
     362       46599 :   }
     363        6580 : };
     364             : 
     365       14402 : } // end namespace llvm
     366             : 
     367           0 : #endif // LLVM_ADT_ITERATOR_H

Generated by: LCOV version 1.13