Repository: dtolnay/cxx
Pull request #538 (2020-12-03 14:29:46)

Implement the random access iterator for rust::Vec
My attempt at addressing #150. 


Patch:
diff --git a/include/cxx.h b/include/cxx.h
index 8c3f2413..cbaf1292 100644
--- a/include/cxx.h
+++ b/include/cxx.h
@@ -293,18 +293,33 @@ private:
 template <typename T>
 class Vec<T>::iterator final {
 public:
-  using difference_type = ptrdiff_t;
+  using iterator_category = std::random_access_iterator_tag;
   using value_type = T;
+  using difference_type = ptrdiff_t;
   using pointer = typename std::add_pointer<T>::type;
   using reference = typename std::add_lvalue_reference<T>::type;
-  using iterator_category = std::forward_iterator_tag;
 
-  T &operator*() const noexcept;
-  T *operator->() const noexcept;
+  reference operator*() const noexcept;
+  pointer operator->() const noexcept;
+  reference operator[](difference_type) const noexcept;
+
   iterator &operator++() noexcept;
   iterator operator++(int) noexcept;
+  iterator &operator--() noexcept;
+  iterator operator--(int) noexcept;
+
+  iterator &operator+=(difference_type) noexcept;
+  iterator &operator-=(difference_type) noexcept;
+  iterator operator+(difference_type) const noexcept;
+  iterator operator-(difference_type) const noexcept;
+  difference_type operator-(const iterator &) const noexcept;
+
   bool operator==(const iterator &) const noexcept;
   bool operator!=(const iterator &) const noexcept;
+  bool operator<(const iterator &) const noexcept;
+  bool operator>(const iterator &) const noexcept;
+  bool operator<=(const iterator &) const noexcept;
+  bool operator>=(const iterator &) const noexcept;
 
 private:
   friend class Vec;
@@ -737,15 +752,22 @@ void Vec<T>::emplace_back(Args &&... args) {
 }
 
 template <typename T>
-T &Vec<T>::iterator::operator*() const noexcept {
+typename Vec<T>::iterator::reference Vec<T>::iterator::operator*() const noexcept {
   return *static_cast<T *>(this->pos);
 }
 
 template <typename T>
-T *Vec<T>::iterator::operator->() const noexcept {
+typename Vec<T>::iterator::pointer Vec<T>::iterator::operator->() const noexcept {
   return static_cast<T *>(this->pos);
 }
 
+template <typename T>
+typename Vec<T>::iterator::reference Vec<T>::iterator::operator[](
+    Vec<T>::iterator::difference_type n) const noexcept {
+  auto pos = static_cast<char *>(this->pos) + this->stride * n;
+  return *static_cast<T *>(pos);
+}
+
 template <typename T>
 typename Vec<T>::iterator &Vec<T>::iterator::operator++() noexcept {
   this->pos = static_cast<char *>(this->pos) + this->stride;
@@ -759,6 +781,57 @@ typename Vec<T>::iterator Vec<T>::iterator::operator++(int) noexcept {
   return ret;
 }
 
+template <typename T>
+typename Vec<T>::iterator &Vec<T>::iterator::operator--() noexcept {
+  this->pos = static_cast<char *>(this->pos) - this->stride;
+  return *this;
+}
+
+template <typename T>
+typename Vec<T>::iterator Vec<T>::iterator::operator--(int) noexcept {
+  auto ret = iterator(*this);
+  this->pos = static_cast<char *>(this->pos) - this->stride;
+  return ret;
+}
+
+template <typename T>
+typename Vec<T>::iterator &
+Vec<T>::iterator::operator+=(Vec<T>::iterator::difference_type n) noexcept {
+  this->pos = static_cast<char *>(this->pos) + this->stride * n;
+  return *this;
+}
+
+template <typename T>
+typename Vec<T>::iterator &
+Vec<T>::iterator::operator-=(Vec<T>::iterator::difference_type n) noexcept {
+  this->pos = static_cast<char *>(this->pos) - this->stride * n;
+  return *this;
+}
+
+template <typename T>
+typename Vec<T>::iterator Vec<T>::iterator::operator+(
+    Vec<T>::iterator::difference_type n) const noexcept {
+  auto temp = iterator(*this);
+  temp.pos = static_cast<char *>(this->pos) + this->stride * n;
+  return temp;
+}
+
+template <typename T>
+typename Vec<T>::iterator Vec<T>::iterator::operator-(
+    Vec<T>::iterator::difference_type n) const noexcept {
+  auto temp = iterator(*this);
+  temp.pos = static_cast<char *>(this->pos) - this->stride * n;
+  return temp;
+}
+
+template <typename T>
+typename Vec<T>::iterator::difference_type
+Vec<T>::iterator::operator-(const iterator &other) const noexcept {
+  auto diff = std::distance(static_cast<char *>(other.pos),
+                            static_cast<char *>(this->pos));
+  return diff / stride;
+}
+
 template <typename T>
 bool Vec<T>::iterator::operator==(const iterator &other) const noexcept {
   return this->pos == other.pos;
@@ -769,6 +842,26 @@ bool Vec<T>::iterator::operator!=(const iterator &other) const noexcept {
   return this->pos != other.pos;
 }
 
+template <typename T>
+bool Vec<T>::iterator::operator>(const iterator &other) const noexcept {
+  return this->pos > other.pos;
+}
+
+template <typename T>
+bool Vec<T>::iterator::operator<(const iterator &other) const noexcept {
+  return this->pos < other.pos;
+}
+
+template <typename T>
+bool Vec<T>::iterator::operator>=(const iterator &other) const noexcept {
+  return this->pos >= other.pos;
+}
+
+template <typename T>
+bool Vec<T>::iterator::operator<=(const iterator &other) const noexcept {
+  return this->pos <= other.pos;
+}
+
 template <typename T>
 typename Vec<T>::iterator Vec<T>::begin() noexcept {
   iterator it;


Test patch:
diff --git a/tests/ffi/lib.rs b/tests/ffi/lib.rs
index 0c2b8b62..ec77594a 100644
--- a/tests/ffi/lib.rs
+++ b/tests/ffi/lib.rs
@@ -133,6 +133,7 @@ pub mod ffi {
         fn c_take_rust_vec_shared_index(v: Vec<Shared>);
         fn c_take_rust_vec_shared_push(v: Vec<Shared>);
         fn c_take_rust_vec_shared_forward_iterator(v: Vec<Shared>);
+        fn c_take_rust_vec_shared_sort(v: Vec<Shared>);
         fn c_take_ref_rust_vec(v: &Vec<u8>);
         fn c_take_ref_rust_vec_string(v: &Vec<String>);
         fn c_take_ref_rust_vec_index(v: &Vec<u8>);
diff --git a/tests/ffi/tests.cc b/tests/ffi/tests.cc
index 47d447cc..485346fe 100644
--- a/tests/ffi/tests.cc
+++ b/tests/ffi/tests.cc
@@ -365,6 +365,16 @@ void c_take_rust_vec_shared_forward_iterator(rust::Vec<Shared> v) {
   }
 }
 
+void c_take_rust_vec_shared_sort(rust::Vec<Shared> v) {
+  // Exercise requirements of RandomAccessIterator.
+  // https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator
+  std::sort(v.begin(), v.end());
+  if (v[0].z == 0 && v[1].z == 2 && v[2].z == 4 && v[3].z == 7)
+  {
+    cxx_test_suite_set_correct();
+  }
+}
+
 void c_take_rust_vec_shared_index(rust::Vec<Shared> v) {
   if (v[0].z == 1010 && v.at(0).z == 1010 && v.front().z == 1010 &&
       v[1].z == 1011 && v.at(1).z == 1011 && v.back().z == 1011) {
diff --git a/tests/ffi/tests.h b/tests/ffi/tests.h
index 0e16ab72..024ecead 100644
--- a/tests/ffi/tests.h
+++ b/tests/ffi/tests.h
@@ -134,6 +134,7 @@ void c_take_rust_vec_string(rust::Vec<rust::String> v);
 void c_take_rust_vec_shared_index(rust::Vec<Shared> v);
 void c_take_rust_vec_shared_push(rust::Vec<Shared> v);
 void c_take_rust_vec_shared_forward_iterator(rust::Vec<Shared> v);
+void c_take_rust_vec_shared_sort(rust::Vec<Shared> v);
 void c_take_ref_rust_vec(const rust::Vec<uint8_t> &v);
 void c_take_ref_rust_vec_string(const rust::Vec<rust::String> &v);
 void c_take_ref_rust_vec_index(const rust::Vec<uint8_t> &v);
diff --git a/tests/test.rs b/tests/test.rs
index d3391520..a2723354 100644
--- a/tests/test.rs
+++ b/tests/test.rs
@@ -149,6 +149,10 @@ fn test_c_take() {
     check!(ffi::c_take_rust_vec_shared_forward_iterator(
         shared_test_vec,
     ));
+    let shared_sort_vec = vec![ffi::Shared { z: 2 }, ffi::Shared { z: 0 }, ffi::Shared { z: 7 }, ffi::Shared { z: 4 }];
+    check!(ffi::c_take_rust_vec_shared_sort(
+        shared_sort_vec,
+    ));
     check!(ffi::c_take_ref_rust_vec(&test_vec));
     check!(ffi::c_take_ref_rust_vec_index(&test_vec));
     check!(ffi::c_take_ref_rust_vec_copy(&test_vec));