| //===-- lld/Core/range.h - Iterator ranges ----------------------*- C++ -*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// \brief Iterator range type based on c++1y range proposal. |
| /// |
| /// See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3350.html |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLD_CORE_RANGE_H |
| #define LLD_CORE_RANGE_H |
| |
| #include "llvm/Support/Compiler.h" |
| #include <array> |
| #include <cassert> |
| #include <iterator> |
| #include <string> |
| #include <type_traits> |
| #include <utility> |
| #include <vector> |
| |
| namespace lld { |
| // Nothing in this namespace is part of the exported interface. |
| namespace detail { |
| using std::begin; |
| using std::end; |
| /// Used as the result type of undefined functions. |
| struct undefined {}; |
| |
| template <typename R> class begin_result { |
| template <typename T> static auto check(T &&t) -> decltype(begin(t)); |
| static undefined check(...); |
| public: |
| typedef decltype(check(std::declval<R>())) type; |
| }; |
| |
| template <typename R> class end_result { |
| template <typename T> static auto check(T &&t) -> decltype(end(t)); |
| static undefined check(...); |
| public: |
| typedef decltype(check(std::declval<R>())) type; |
| }; |
| |
| // Things that begin and end work on, in compatible ways, are |
| // ranges. [stmt.ranged] |
| template <typename R> |
| struct is_range : std::is_same<typename detail::begin_result<R>::type, |
| typename detail::end_result<R>::type> {}; |
| |
| // This currently requires specialization and doesn't work for |
| // detecting \c range<>s or iterators. We should add |
| // \c contiguous_iterator_tag to fix that. |
| template <typename R> struct is_contiguous_range : std::false_type {}; |
| template <typename R> |
| struct is_contiguous_range<R &> : is_contiguous_range<R> {}; |
| template <typename R> |
| struct is_contiguous_range <R &&> : is_contiguous_range<R> {}; |
| template <typename R> |
| struct is_contiguous_range<const R> : is_contiguous_range<R> {}; |
| |
| template <typename T, size_t N> |
| struct is_contiguous_range<T[N]> : std::true_type {}; |
| template <typename T, size_t N> |
| struct is_contiguous_range<const T[N]> : std::true_type {}; |
| template <typename T, size_t N> |
| struct is_contiguous_range<std::array<T, N> > : std::true_type {}; |
| template <typename charT, typename traits, typename Allocator> |
| struct is_contiguous_range< |
| std::basic_string<charT, traits, Allocator> > : std::true_type {}; |
| template <typename T, typename Allocator> |
| struct is_contiguous_range<std::vector<T, Allocator> > : std::true_type {}; |
| |
| // Removes cv qualifiers from all levels of a multi-level pointer |
| // type, not just the type level. |
| template <typename T> struct remove_all_cv_ptr { |
| typedef T type; |
| }; |
| template <typename T> struct remove_all_cv_ptr<T *> { |
| typedef typename remove_all_cv_ptr<T>::type *type; |
| }; |
| template <typename T> struct remove_all_cv_ptr<const T> { |
| typedef typename remove_all_cv_ptr<T>::type type; |
| }; |
| template <typename T> struct remove_all_cv_ptr<volatile T> { |
| typedef typename remove_all_cv_ptr<T>::type type; |
| }; |
| template <typename T> struct remove_all_cv_ptr<const volatile T> { |
| typedef typename remove_all_cv_ptr<T>::type type; |
| }; |
| |
| template <typename From, typename To> |
| struct conversion_preserves_array_indexing : std::false_type {}; |
| |
| template <typename FromVal, typename ToVal> |
| struct conversion_preserves_array_indexing<FromVal *, |
| ToVal *> : std::integral_constant< |
| bool, std::is_convertible<FromVal *, ToVal *>::value && |
| std::is_same<typename remove_all_cv_ptr<FromVal>::type, |
| typename remove_all_cv_ptr<ToVal>::type>::value> {}; |
| |
| template <typename T> |
| LLVM_CONSTEXPR auto adl_begin(T &&t) -> decltype(begin(t)) { |
| return begin(std::forward<T>(t)); |
| } |
| |
| template <typename T> LLVM_CONSTEXPR auto adl_end(T &&t) -> decltype(end(t)) { |
| return end(std::forward<T>(t)); |
| } |
| } // end namespace detail |
| |
| /// A \c std::range<Iterator> represents a half-open iterator range |
| /// built from two iterators, \c 'begin', and \c 'end'. If \c end is |
| /// not reachable from \c begin, the behavior is undefined. |
| /// |
| /// The mutability of elements of the range is controlled by the |
| /// Iterator argument. Instantiate |
| /// <code>range<<var>Foo</var>::iterator></code> or |
| /// <code>range<<var>T</var>*></code>, or call |
| /// <code>make_range(<var>non_const_container</var>)</code>, and you |
| /// get a mutable range. Instantiate |
| /// <code>range<<var>Foo</var>::const_iterator></code> or |
| /// <code>range<const <var>T</var>*></code>, or call |
| /// <code>make_range(<var>const_container</var>)</code>, and you get a |
| /// constant range. |
| /// |
| /// \todo Inherit from std::pair<Iterator, Iterator>? |
| /// |
| /// \todo This interface contains some functions that could be |
| /// provided as free algorithms rather than member functions, and all |
| /// of the <code>pop_*()</code> functions could be replaced by \c |
| /// slice() at the cost of some extra iterator copies. This makes |
| /// them more awkward to use, but makes it easier for users to write |
| /// their own types that follow the same interface. On the other hand, |
| /// a \c range_facade could be provided to help users write new |
| /// ranges, and it could provide the members. Such functions are |
| /// marked with a note in their documentation. (Of course, all of |
| /// these member functions could be provided as free functions using |
| /// the iterator access methods, but one goal here is to allow people |
| /// to program without touching iterators at all.) |
| template <typename Iterator> class range { |
| Iterator begin_, end_; |
| public: |
| /// \name types |
| /// @{ |
| |
| /// The iterator category of \c Iterator. |
| /// \todo Consider defining range categories. If they don't add |
| /// anything over the corresponding iterator categories, then |
| /// they're probably not worth defining. |
| typedef typename std::iterator_traits< |
| Iterator>::iterator_category iterator_category; |
| /// The type of elements of the range. Not cv-qualified. |
| typedef typename std::iterator_traits<Iterator>::value_type value_type; |
| /// The type of the size of the range and offsets within the range. |
| typedef typename std::iterator_traits< |
| Iterator>::difference_type difference_type; |
| /// The return type of element access methods: \c front(), \c back(), etc. |
| typedef typename std::iterator_traits<Iterator>::reference reference; |
| typedef typename std::iterator_traits<Iterator>::pointer pointer; |
| /// @} |
| |
| /// \name constructors |
| /// @{ |
| |
| /// Creates a range of default-constructed (<em>not</em> |
| /// value-initialized) iterators. For most \c Iterator types, this |
| /// will be an invalid range. |
| range() : begin_(), end_() {} |
| |
| /// \pre \c end is reachable from \c begin. |
| /// \post <code>this->begin() == begin && this->end() == end</code> |
| LLVM_CONSTEXPR range(Iterator begin, Iterator end) |
| : begin_(begin), end_(end) {} |
| |
| /// \par Participates in overload resolution if: |
| /// - \c Iterator is not a pointer type, |
| /// - \c begin(r) and \c end(r) return the same type, and |
| /// - that type is convertible to \c Iterator. |
| /// |
| /// \todo std::begin and std::end are overloaded between T& and |
| /// const T&, which means that if a container has only a non-const |
| /// begin or end method, then it's ill-formed to pass an rvalue to |
| /// the free function. To avoid that problem, we don't use |
| /// std::forward<> here, so begin() and end() are always called with |
| /// an lvalue. Another option would be to insist that rvalue |
| /// arguments to range() must have const begin() and end() methods. |
| template <typename R> LLVM_CONSTEXPR range( |
| R &&r, |
| typename std::enable_if< |
| !std::is_pointer<Iterator>::value && |
| detail::is_range<R>::value && |
| std::is_convertible<typename detail::begin_result<R>::type, |
| Iterator>::value>::type* = 0) |
| : begin_(detail::adl_begin(r)), end_(detail::adl_end(r)) {} |
| |
| /// This constructor creates a \c range<T*> from any range with |
| /// contiguous iterators. Because dereferencing a past-the-end |
| /// iterator can be undefined behavior, empty ranges get initialized |
| /// with \c nullptr rather than \c &*begin(). |
| /// |
| /// \par Participates in overload resolution if: |
| /// - \c Iterator is a pointer type \c T*, |
| /// - \c begin(r) and \c end(r) return the same type, |
| /// - elements \c i of that type satisfy the invariant |
| /// <code>&*(i + N) == (&*i) + N</code>, and |
| /// - The result of <code>&*begin()</code> is convertible to \c T* |
| /// using only qualification conversions [conv.qual] (since |
| /// pointer conversions stop the pointer from pointing to an |
| /// array element). |
| /// |
| /// \todo The <code>&*(i + N) == (&*i) + N</code> invariant is |
| /// currently impossible to check for user-defined types. We need a |
| /// \c contiguous_iterator_tag to let users assert it. |
| template <typename R> LLVM_CONSTEXPR range( |
| R &&r, |
| typename std::enable_if< |
| std::is_pointer<Iterator>::value && |
| detail::is_contiguous_range<R>::value |
| // MSVC returns false for this in this context, but not if we lift it out of the |
| // constructor. |
| #ifndef _MSC_VER |
| && detail::conversion_preserves_array_indexing< |
| decltype(&*detail::adl_begin(r)), Iterator>::value |
| #endif |
| >::type* = 0) |
| : begin_((detail::adl_begin(r) == detail::adl_end(r) && |
| !std::is_pointer<decltype(detail::adl_begin(r))>::value) |
| // For non-pointers, &*begin(r) is only defined behavior |
| // if there's an element there. Otherwise, use nullptr |
| // since the user can't dereference it anyway. This _is_ |
| // detectable. |
| ? nullptr : &*detail::adl_begin(r)), |
| end_(begin_ + (detail::adl_end(r) - detail::adl_begin(r))) {} |
| |
| /// @} |
| |
| /// \name iterator access |
| /// @{ |
| LLVM_CONSTEXPR Iterator begin() const { return begin_; } |
| LLVM_CONSTEXPR Iterator end() const { return end_; } |
| /// @} |
| |
| /// \name element access |
| /// @{ |
| |
| /// \par Complexity: |
| /// O(1) |
| /// \pre \c !empty() |
| /// \returns a reference to the element at the front of the range. |
| LLVM_CONSTEXPR reference front() const { return *begin(); } |
| |
| /// \par Ill-formed unless: |
| /// \c iterator_category is convertible to \c |
| /// std::bidirectional_iterator_tag. |
| /// |
| /// \par Complexity: |
| /// O(2) (Involves copying and decrementing an iterator, so not |
| /// quite as cheap as \c front()) |
| /// |
| /// \pre \c !empty() |
| /// \returns a reference to the element at the front of the range. |
| LLVM_CONSTEXPR reference back() const { |
| static_assert( |
| std::is_convertible<iterator_category, |
| std::bidirectional_iterator_tag>::value, |
| "Can only retrieve the last element of a bidirectional range."); |
| using std::prev; |
| return *prev(end()); |
| } |
| |
| /// This method is drawn from scripting language indexing. It |
| /// indexes std::forward from the beginning of the range if the argument |
| /// is positive, or backwards from the end of the array if the |
| /// argument is negative. |
| /// |
| /// \par Ill-formed unless: |
| /// \c iterator_category is convertible to \c |
| /// std::random_access_iterator_tag. |
| /// |
| /// \par Complexity: |
| /// O(1) |
| /// |
| /// \pre <code>abs(index) < size() || index == -size()</code> |
| /// |
| /// \returns if <code>index >= 0</code>, a reference to the |
| /// <code>index</code>'th element in the range. Otherwise, a |
| /// reference to the <code>size()+index</code>'th element. |
| LLVM_CONSTEXPR reference operator[](difference_type index) const { |
| static_assert(std::is_convertible<iterator_category, |
| std::random_access_iterator_tag>::value, |
| "Can only index into a random-access range."); |
| // Less readable construction for constexpr support. |
| return index < 0 ? end()[index] |
| : begin()[index]; |
| } |
| /// @} |
| |
| /// \name size |
| /// @{ |
| |
| /// \par Complexity: |
| /// O(1) |
| /// \returns \c true if the range contains no elements. |
| LLVM_CONSTEXPR bool empty() const { return begin() == end(); } |
| |
| /// \par Ill-formed unless: |
| /// \c iterator_category is convertible to |
| /// \c std::forward_iterator_tag. |
| /// |
| /// \par Complexity: |
| /// O(1) if \c iterator_category is convertible to \c |
| /// std::random_access_iterator_tag. O(<code>size()</code>) |
| /// otherwise. |
| /// |
| /// \returns the number of times \c pop_front() can be called before |
| /// \c empty() becomes true. |
| LLVM_CONSTEXPR difference_type size() const { |
| static_assert(std::is_convertible<iterator_category, |
| std::forward_iterator_tag>::value, |
| "Calling size on an input range would destroy the range."); |
| return dispatch_size(iterator_category()); |
| } |
| /// @} |
| |
| /// \name traversal from the beginning of the range |
| /// @{ |
| |
| /// Advances the beginning of the range by one element. |
| /// \pre \c !empty() |
| void pop_front() { ++begin_; } |
| |
| /// Advances the beginning of the range by \c n elements. |
| /// |
| /// \par Complexity: |
| /// O(1) if \c iterator_category is convertible to \c |
| /// std::random_access_iterator_tag, O(<code>n</code>) otherwise. |
| /// |
| /// \pre <code>n >= 0</code>, and there must be at least \c n |
| /// elements in the range. |
| void pop_front(difference_type n) { advance(begin_, n); } |
| |
| /// Advances the beginning of the range by at most \c n elements, |
| /// stopping if the range becomes empty. A negative argument causes |
| /// no change. |
| /// |
| /// \par Complexity: |
| /// O(1) if \c iterator_category is convertible to \c |
| /// std::random_access_iterator_tag, O(<code>min(n, |
| /// <var>#-elements-in-range</var>)</code>) otherwise. |
| /// |
| /// \note Could be provided as a free function with little-to-no |
| /// loss in efficiency. |
| void pop_front_upto(difference_type n) { |
| advance_upto(begin_, std::max<difference_type>(0, n), end_, |
| iterator_category()); |
| } |
| |
| /// @} |
| |
| /// \name traversal from the end of the range |
| /// @{ |
| |
| /// Moves the end of the range earlier by one element. |
| /// |
| /// \par Ill-formed unless: |
| /// \c iterator_category is convertible to |
| /// \c std::bidirectional_iterator_tag. |
| /// |
| /// \par Complexity: |
| /// O(1) |
| /// |
| /// \pre \c !empty() |
| void pop_back() { |
| static_assert(std::is_convertible<iterator_category, |
| std::bidirectional_iterator_tag>::value, |
| "Can only access the end of a bidirectional range."); |
| --end_; |
| } |
| |
| /// Moves the end of the range earlier by \c n elements. |
| /// |
| /// \par Ill-formed unless: |
| /// \c iterator_category is convertible to |
| /// \c std::bidirectional_iterator_tag. |
| /// |
| /// \par Complexity: |
| /// O(1) if \c iterator_category is convertible to \c |
| /// std::random_access_iterator_tag, O(<code>n</code>) otherwise. |
| /// |
| /// \pre <code>n >= 0</code>, and there must be at least \c n |
| /// elements in the range. |
| void pop_back(difference_type n) { |
| static_assert(std::is_convertible<iterator_category, |
| std::bidirectional_iterator_tag>::value, |
| "Can only access the end of a bidirectional range."); |
| advance(end_, -n); |
| } |
| |
| /// Moves the end of the range earlier by <code>min(n, |
| /// size())</code> elements. A negative argument causes no change. |
| /// |
| /// \par Ill-formed unless: |
| /// \c iterator_category is convertible to |
| /// \c std::bidirectional_iterator_tag. |
| /// |
| /// \par Complexity: |
| /// O(1) if \c iterator_category is convertible to \c |
| /// std::random_access_iterator_tag, O(<code>min(n, |
| /// <var>#-elements-in-range</var>)</code>) otherwise. |
| /// |
| /// \note Could be provided as a free function with little-to-no |
| /// loss in efficiency. |
| void pop_back_upto(difference_type n) { |
| static_assert(std::is_convertible<iterator_category, |
| std::bidirectional_iterator_tag>::value, |
| "Can only access the end of a bidirectional range."); |
| advance_upto(end_, -std::max<difference_type>(0, n), begin_, |
| iterator_category()); |
| } |
| |
| /// @} |
| |
| /// \name creating derived ranges |
| /// @{ |
| |
| /// Divides the range into two pieces at \c index, where a positive |
| /// \c index represents an offset from the beginning of the range |
| /// and a negative \c index represents an offset from the end. |
| /// <code>range[index]</code> is the first element in the second |
| /// piece. If <code>index >= size()</code>, the second piece |
| /// will be empty. If <code>index < -size()</code>, the first |
| /// piece will be empty. |
| /// |
| /// \par Ill-formed unless: |
| /// \c iterator_category is convertible to |
| /// \c std::forward_iterator_tag. |
| /// |
| /// \par Complexity: |
| /// - If \c iterator_category is convertible to \c |
| /// std::random_access_iterator_tag: O(1) |
| /// - Otherwise, if \c iterator_category is convertible to \c |
| /// std::bidirectional_iterator_tag, \c abs(index) iterator increments |
| /// or decrements |
| /// - Otherwise, if <code>index >= 0</code>, \c index iterator |
| /// increments |
| /// - Otherwise, <code>size() + (size() + index)</code> |
| /// iterator increments. |
| /// |
| /// \returns a pair of adjacent ranges. |
| /// |
| /// \post |
| /// - <code>result.first.size() == min(index, this->size())</code> |
| /// - <code>result.first.end() == result.second.begin()</code> |
| /// - <code>result.first.size() + result.second.size()</code> <code>== |
| /// this->size()</code> |
| /// |
| /// \todo split() could take an arbitrary number of indices and |
| /// return an <code>N+1</code>-element \c tuple<>. This is tricky to |
| /// implement with negative indices in the optimal number of |
| /// increments or decrements for a bidirectional iterator, but it |
| /// should be possible. Do we want it? |
| std::pair<range, range> split(difference_type index) const { |
| static_assert( |
| std::is_convertible<iterator_category, |
| std::forward_iterator_tag>::value, |
| "Calling split on a non-std::forward range would return a useless " |
| "first result."); |
| if (index >= 0) { |
| range second = *this; |
| second.pop_front_upto(index); |
| return make_pair(range(begin(), second.begin()), second); |
| } else { |
| return dispatch_split_neg(index, iterator_category()); |
| } |
| } |
| |
| /// \returns A sub-range from \c start to \c stop (not including \c |
| /// stop, as usual). \c start and \c stop are interpreted as for |
| /// <code>operator[]</code>, with negative values offsetting from |
| /// the end of the range. Omitting the \c stop argument makes the |
| /// sub-range continue to the end of the original range. Positive |
| /// arguments saturate to the end of the range, and negative |
| /// arguments saturate to the beginning. If \c stop is before \c |
| /// start, returns an empty range beginning and ending at \c start. |
| /// |
| /// \par Ill-formed unless: |
| /// \c iterator_category is convertible to |
| /// \c std::forward_iterator_tag. |
| /// |
| /// \par Complexity: |
| /// - If \c iterator_category is convertible to \c |
| /// std::random_access_iterator_tag: O(1) |
| /// - Otherwise, if \c iterator_category is convertible to \c |
| /// std::bidirectional_iterator_tag, at most <code>min(abs(start), |
| /// size()) + min(abs(stop), size())</code> iterator |
| /// increments or decrements |
| /// - Otherwise, if <code>start >= 0 && stop >= 0</code>, |
| /// <code>max(start, stop)</code> iterator increments |
| /// - Otherwise, <code>size() + max(start', stop')</code> |
| /// iterator increments, where \c start' and \c stop' are the |
| /// offsets of the elements \c start and \c stop refer to. |
| /// |
| /// \note \c slice(start) should be implemented with a different |
| /// overload, rather than defaulting \c stop to |
| /// <code>numeric_limits<difference_type>::max()</code>, because |
| /// using a default would force non-random-access ranges to use an |
| /// O(<code>size()</code>) algorithm to compute the end rather |
| /// than the O(1) they're capable of. |
| range slice(difference_type start, difference_type stop) const { |
| static_assert( |
| std::is_convertible<iterator_category, |
| std::forward_iterator_tag>::value, |
| "Calling slice on a non-std::forward range would destroy the original " |
| "range."); |
| return dispatch_slice(start, stop, iterator_category()); |
| } |
| |
| range slice(difference_type start) const { |
| static_assert( |
| std::is_convertible<iterator_category, |
| std::forward_iterator_tag>::value, |
| "Calling slice on a non-std::forward range would destroy the original " |
| "range."); |
| return split(start).second; |
| } |
| |
| /// @} |
| |
| private: |
| // advance_upto: should be added to <algorithm>, but I'll use it as |
| // a helper function here. |
| // |
| // These return the number of increments that weren't applied |
| // because we ran into 'limit' (or 0 if we didn't run into limit). |
| static difference_type advance_upto(Iterator &it, difference_type n, |
| Iterator limit, std::input_iterator_tag) { |
| if (n < 0) |
| return 0; |
| while (it != limit && n > 0) { |
| ++it; |
| --n; |
| } |
| return n; |
| } |
| |
| static difference_type advance_upto(Iterator &it, difference_type n, |
| Iterator limit, |
| std::bidirectional_iterator_tag) { |
| if (n < 0) { |
| while (it != limit && n < 0) { |
| --it; |
| ++n; |
| } |
| } else { |
| while (it != limit && n > 0) { |
| ++it; |
| --n; |
| } |
| } |
| return n; |
| } |
| |
| static difference_type advance_upto(Iterator &it, difference_type n, |
| Iterator limit, |
| std::random_access_iterator_tag) { |
| difference_type distance = limit - it; |
| if (distance < 0) |
| assert(n <= 0); |
| else if (distance > 0) |
| assert(n >= 0); |
| |
| if (abs(distance) > abs(n)) { |
| it += n; |
| return 0; |
| } else { |
| it = limit; |
| return n - distance; |
| } |
| } |
| |
| // Dispatch functions. |
| difference_type dispatch_size(std::forward_iterator_tag) const { |
| return std::distance(begin(), end()); |
| } |
| |
| LLVM_CONSTEXPR difference_type dispatch_size( |
| std::random_access_iterator_tag) const { |
| return end() - begin(); |
| } |
| |
| std::pair<range, range> dispatch_split_neg(difference_type index, |
| std::forward_iterator_tag) const { |
| assert(index < 0); |
| difference_type size = this->size(); |
| return split(std::max<difference_type>(0, size + index)); |
| } |
| |
| std::pair<range, range> dispatch_split_neg( |
| difference_type index, std::bidirectional_iterator_tag) const { |
| assert(index < 0); |
| range first = *this; |
| first.pop_back_upto(-index); |
| return make_pair(first, range(first.end(), end())); |
| } |
| |
| range dispatch_slice(difference_type start, difference_type stop, |
| std::forward_iterator_tag) const { |
| if (start < 0 || stop < 0) { |
| difference_type size = this->size(); |
| if (start < 0) |
| start = std::max<difference_type>(0, size + start); |
| if (stop < 0) |
| stop = size + stop; // Possibly negative; will be fixed in 2 lines. |
| } |
| stop = std::max<difference_type>(start, stop); |
| |
| Iterator first = begin(); |
| advance_upto(first, start, end(), iterator_category()); |
| Iterator last = first; |
| advance_upto(last, stop - start, end(), iterator_category()); |
| return range(first, last); |
| } |
| |
| range dispatch_slice(const difference_type start, const difference_type stop, |
| std::bidirectional_iterator_tag) const { |
| Iterator first; |
| if (start < 0) { |
| first = end(); |
| advance_upto(first, start, begin(), iterator_category()); |
| } else { |
| first = begin(); |
| advance_upto(first, start, end(), iterator_category()); |
| } |
| Iterator last; |
| if (stop < 0) { |
| last = end(); |
| advance_upto(last, stop, first, iterator_category()); |
| } else { |
| if (start >= 0) { |
| last = first; |
| if (stop > start) |
| advance_upto(last, stop - start, end(), iterator_category()); |
| } else { |
| // Complicated: 'start' walked from the end of the sequence, |
| // but 'stop' needs to walk from the beginning. |
| Iterator dummy = begin(); |
| // Walk up to 'stop' increments from begin(), stopping when we |
| // get to 'first', and capturing the remaining number of |
| // increments. |
| difference_type increments_past_start = |
| advance_upto(dummy, stop, first, iterator_category()); |
| if (increments_past_start == 0) { |
| // If this is 0, then stop was before start. |
| last = first; |
| } else { |
| // Otherwise, count that many spaces beyond first. |
| last = first; |
| advance_upto(last, increments_past_start, end(), iterator_category()); |
| } |
| } |
| } |
| return range(first, last); |
| } |
| |
| range dispatch_slice(difference_type start, difference_type stop, |
| std::random_access_iterator_tag) const { |
| const difference_type size = this->size(); |
| if (start < 0) |
| start = size + start; |
| if (start < 0) |
| start = 0; |
| if (start > size) |
| start = size; |
| |
| if (stop < 0) |
| stop = size + stop; |
| if (stop < start) |
| stop = start; |
| if (stop > size) |
| stop = size; |
| |
| return range(begin() + start, begin() + stop); |
| } |
| }; |
| |
| /// \name deducing constructor wrappers |
| /// \relates std::range |
| /// \xmlonly <nonmember/> \endxmlonly |
| /// |
| /// These functions do the same thing as the constructor with the same |
| /// signature. They just allow users to avoid writing the iterator |
| /// type. |
| /// @{ |
| |
| /// \todo I'd like to define a \c make_range taking a single iterator |
| /// argument representing the beginning of a range that ends with a |
| /// default-constructed \c Iterator. This would help with using |
| /// iterators like \c istream_iterator. However, using just \c |
| /// make_range() could be confusing and lead to people writing |
| /// incorrect ranges of more common iterators. Is there a better name? |
| template <typename Iterator> |
| LLVM_CONSTEXPR range<Iterator> make_range(Iterator begin, Iterator end) { |
| return range<Iterator>(begin, end); |
| } |
| |
| /// \par Participates in overload resolution if: |
| /// \c begin(r) and \c end(r) return the same type. |
| template <typename Range> LLVM_CONSTEXPR auto make_range( |
| Range &&r, |
| typename std::enable_if<detail::is_range<Range>::value>::type* = 0) |
| -> range<decltype(detail::adl_begin(r))> { |
| return range<decltype(detail::adl_begin(r))>(r); |
| } |
| |
| /// \par Participates in overload resolution if: |
| /// - \c begin(r) and \c end(r) return the same type, |
| /// - that type satisfies the invariant that <code>&*(i + N) == |
| /// (&*i) + N</code>, and |
| /// - \c &*begin(r) has a pointer type. |
| template <typename Range> LLVM_CONSTEXPR auto make_ptr_range( |
| Range &&r, |
| typename std::enable_if< |
| detail::is_contiguous_range<Range>::value && |
| std::is_pointer<decltype(&*detail::adl_begin(r))>::value>::type* = 0) |
| -> range<decltype(&*detail::adl_begin(r))> { |
| return range<decltype(&*detail::adl_begin(r))>(r); |
| } |
| /// @} |
| } // end namespace lld |
| |
| #endif |