text: // Copyright 2018 The Chromium Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  
  #ifndef BASE_CONTAINERS_CHECKED_ITERATORS_H_
  #define BASE_CONTAINERS_CHECKED_ITERATORS_H_
  
  #include <iterator>
  #include <memory>
  #include <type_traits>
  
  #include "base/containers/util.h"
  #include "base/logging.h"
  
  namespace base {
  
  template <typename T>
  class CheckedContiguousIterator {
   public:
    using difference_type = std::ptrdiff_t;
    using value_type = std::remove_cv_t<T>;
    using pointer = T*;
    using reference = T&;
    using iterator_category = std::random_access_iterator_tag;
  
    // Required for converting constructor below.
    template <typename U>
    friend class CheckedContiguousIterator;
  
    constexpr CheckedContiguousIterator() = default;
    constexpr CheckedContiguousIterator(T* start, const T* end)
        : CheckedContiguousIterator(start, start, end) {}
    constexpr CheckedContiguousIterator(const T* start, T* current, const T* end)
        : start_(start), current_(current), end_(end) {
      CHECK_LE(start, current);
      CHECK_LE(current, end);
    }
    constexpr CheckedContiguousIterator(const CheckedContiguousIterator& other) =
        default;
  
    // Converting constructor allowing conversions like CCI<T> to CCI<const T>,
    // but disallowing CCI<const T> to CCI<T> or CCI<Derived> to CCI<Base>, which
    // are unsafe. Furthermore, this is the same condition as used by the
    // converting constructors of std::span<T> and std::unique_ptr<T[]>.
    // See https://wg21.link/n4042 for details.
    template <
        typename U,
        std::enable_if_t<std::is_convertible<U (*)[], T (*)[]>::value>* = nullptr>
    constexpr CheckedContiguousIterator(const CheckedContiguousIterator<U>& other)
        : start_(other.start_), current_(other.current_), end_(other.end_) {
      // We explicitly don't delegate to the 3-argument constructor here. Its
      // CHECKs would be redundant, since we expect |other| to maintain its own
      // invariant. However, DCHECKs never hurt anybody. Presumably.
      DCHECK_LE(other.start_, other.current_);
      DCHECK_LE(other.current_, other.end_);
    }
  
    ~CheckedContiguousIterator() = default;
  
    constexpr CheckedContiguousIterator& operator=(
        const CheckedContiguousIterator& other) = default;
  
    friend constexpr bool operator==(const CheckedContiguousIterator& lhs,
                                     const CheckedContiguousIterator& rhs) {
      lhs.CheckComparable(rhs);
      return lhs.current_ == rhs.current_;
    }
  
    friend constexpr bool operator!=(const CheckedContiguousIterator& lhs,
                                     const CheckedContiguousIterator& rhs) {
      lhs.CheckComparable(rhs);
      return lhs.current_ != rhs.current_;
    }
  
    friend constexpr bool operator<(const CheckedContiguousIterator& lhs,
                                    const CheckedContiguousIterator& rhs) {
      lhs.CheckComparable(rhs);
      return lhs.current_ < rhs.current_;
    }
  
    friend constexpr bool operator<=(const CheckedContiguousIterator& lhs,
                                     const CheckedContiguousIterator& rhs) {
      lhs.CheckComparable(rhs);
      return lhs.current_ <= rhs.current_;
    }
    friend constexpr bool operator>(const CheckedContiguousIterator& lhs,
                                    const CheckedContiguousIterator& rhs) {
      lhs.CheckComparable(rhs);
      return lhs.current_ > rhs.current_;
    }
  
    friend constexpr bool operator>=(const CheckedContiguousIterator& lhs,
                                     const CheckedContiguousIterator& rhs) {
      lhs.CheckComparable(rhs);
      return lhs.current_ >= rhs.current_;
    }
  
    constexpr CheckedContiguousIterator& operator++() {
      CHECK_NE(current_, end_);
      ++current_;
      return *this;
    }
  
    constexpr CheckedContiguousIterator operator++(int) {
      CheckedContiguousIterator old = *this;
      ++*this;
      return old;
    }
  
    constexpr CheckedContiguousIterator& operator--() {
      CHECK_NE(current_, start_);
      --current_;
      return *this;
    }
  
    constexpr CheckedContiguousIterator operator--(int) {
      CheckedContiguousIterator old = *this;
      --*this;
      return old;
    }
  
    constexpr CheckedContiguousIterator& operator+=(difference_type rhs) {
      if (rhs > 0) {
        CHECK_LE(rhs, end_ - current_);
      } else {
        CHECK_LE(-rhs, current_ - start_);
      }
      current_ += rhs;
      return *this;
    }
  
    constexpr CheckedContiguousIterator operator+(difference_type rhs) const {
      CheckedContiguousIterator it = *this;
      it += rhs;
      return it;
    }
  
    constexpr CheckedContiguousIterator& operator-=(difference_type rhs) {
      if (rhs < 0) {
        CHECK_LE(-rhs, end_ - current_);
      } else {
        CHECK_LE(rhs, current_ - start_);
      }
      current_ -= rhs;
      return *this;
    }
  
    constexpr CheckedContiguousIterator operator-(difference_type rhs) const {
      CheckedContiguousIterator it = *this;
      it -= rhs;
      return it;
    }
  
    constexpr friend difference_type operator-(
        const CheckedContiguousIterator& lhs,
        const CheckedContiguousIterator& rhs) {
      lhs.CheckComparable(rhs);
      return lhs.current_ - rhs.current_;
    }
  
    constexpr reference operator*() const {
      CHECK_NE(current_, end_);
      return *current_;
    }
  
    constexpr pointer operator->() const {
      CHECK_NE(current_, end_);
      return current_;
    }
  
    constexpr reference operator[](difference_type rhs) const {
      CHECK_GE(rhs, 0);
      CHECK_LT(rhs, end_ - current_);
      return current_[rhs];
    }
  
    static bool IsRangeMoveSafe(const CheckedContiguousIterator& from_begin,
                                const CheckedContiguousIterator& from_end,
                                const CheckedContiguousIterator& to)
        WARN_UNUSED_RESULT {
      if (from_end < from_begin)
        return false;
      const auto from_begin_uintptr = get_uintptr(from_begin.current_);
      const auto from_end_uintptr = get_uintptr(from_end.current_);
      const auto to_begin_uintptr = get_uintptr(to.current_);
      const auto to_end_uintptr =
          get_uintptr((to + std::distance(from_begin, from_end)).current_);
  
      return to_begin_uintptr >= from_end_uintptr ||
             to_end_uintptr <= from_begin_uintptr;
    }
  
   private:
    constexpr void CheckComparable(const CheckedContiguousIterator& other) const {
      CHECK_EQ(start_, other.start_);
      CHECK_EQ(end_, other.end_);
    }
  
    const T* start_ = nullptr;
    T* current_ = nullptr;
    const T* end_ = nullptr;
  };
  
  template <typename T>
  using CheckedContiguousConstIterator = CheckedContiguousIterator<const T>;
  
  }  // namespace base
  
  #endif  // BASE_CONTAINERS_CHECKED_ITERATORS_H_
  