Repository: jorgecarleitao/arrow2 (rust)

Issue:
slice and dice stresstest Utf8Array
This slicing stress test will make us more sure of the future. :slightly_smiling_face: (once it passes)

## Cargo.toml
```
[dependencies]
arrow = { package = "arrow2", git = "https://github.com/jorgecarleitao/arrow2", rev = "86edfd639b33d9fbc468e2f68bb6ce41de52f95e", default-features = false, features=["compute"]}
rand = "0.8"
```

## main.rs
```rust
use rand::Rng;
use arrow::array::{Utf8Array, BooleanArray, Array};
use rand::distributions::{
    Alphanumeric, Uniform, Bernoulli
};
use arrow::compute::filter::filter;
use std::iter::FromIterator;

fn main() {
    let mut rng = rand::thread_rng();
    let length = 50000;

    let values_iter = (0..length).map(|_| {
        let len = (&mut rng).sample(Uniform::new(0usize, 8));
        let s: String = (&mut rng).sample_iter(&Alphanumeric).take(len).map(char::from).collect();
        s
    });


    let arr = Utf8Array::<i32>::from_iter_values(values_iter);
    let values_iter = (0..length).map(|_| {
        let v: bool = (&mut rng).sample(Bernoulli::new(0.5).unwrap());
        Some(v)
    });
    let mask = BooleanArray::from_iter(values_iter);

    for offset in 100usize..(length - 1) {
        let len = (&mut rng).sample(Uniform::new(0, length - offset));
        let arr_s = arr.slice(offset, len);
        let mask_s = mask.slice(offset, len);

        filter(&arr_s, &mask_s).unwrap();
    }
}
```

## Run
`RUST_BACKTRACE=1 cargo run --release`

## Panic

```
thread 'main' panicked at 'range end index 41006 out of range for slice of length 41001', /home/ritchie46/.cargo/git/checkouts/arrow2-8a2ad61d97265680/86edfd6/src/array/growable/utf8.rs:75:14
stack backtrace:
   0: rust_begin_unwind
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/std/src/panicking.rs:516:5
   1: core::panicking::panic_fmt
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/core/src/panicking.rs:93:14
   2: core::slice::index::slice_end_index_len_fail
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/core/src/slice/index.rs:41:5
   3: <core::ops::range::Range<usize> as core::slice::index::SliceIndex<[T]>>::index
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/core/src/slice/index.rs:240:13
   4: core::slice::index::<impl core::ops::index::Index<I> for [T]>::index
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/core/src/slice/index.rs:15:9
   5: <arrow2::array::growable::utf8::GrowableUtf8<O> as arrow2::array::growable::Growable>::extend
             at /home/ritchie46/.cargo/git/checkouts/arrow2-8a2ad61d97265680/86edfd6/src/array/growable/utf8.rs:75:14
   6: arrow2::compute::filter::filter::{{closure}}
             at /home/ritchie46/.cargo/git/checkouts/arrow2-8a2ad61d97265680/86edfd6/src/compute/filter.rs:244:42
   7: core::iter::traits::iterator::Iterator::for_each::call::{{closure}}
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/core/src/iter/traits/iterator.rs:734:29
   8: core::iter::traits::iterator::Iterator::fold
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/core/src/iter/traits/iterator.rs:2174:21
   9: core::iter::traits::iterator::Iterator::for_each
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/core/src/iter/traits/iterator.rs:737:9
  10: arrow2::compute::filter::filter
             at /home/ritchie46/.cargo/git/checkouts/arrow2-8a2ad61d97265680/86edfd6/src/compute/filter.rs:244:13
  11: memcheck::main
             at ./src/main.rs:32:9
  12: core::ops::function::FnOnce::call_once
             at /rustc/492723897e9b4db6701b3a75b72618d08a7d5319/library/core/src/ops/function.rs:227:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

```

Pull request description:
Fixed error in computing slices of set bitmaps.
The slice iterator could go beyond bounds, which would trigger a panic e.g. in `filter`. This PR fixes this.

Closes #292 


Patch:
diff --git a/src/array/primitive/mutable.rs b/src/array/primitive/mutable.rs
index 69220c3cfa..2e80840249 100644
--- a/src/array/primitive/mutable.rs
+++ b/src/array/primitive/mutable.rs
@@ -222,9 +222,9 @@ impl<T: NativeType> MutablePrimitiveArray<T> {
         if value.is_none() && self.validity.is_none() {
             // When the validity is None, all elements so far are valid. When one of the elements is set fo null,
             // the validity must be initialized.
-            self.validity = Some(MutableBitmap::from_trusted_len_iter(
-                std::iter::repeat(true).take(self.len()),
-            ));
+            let mut validity = MutableBitmap::new();
+            validity.extend_constant(self.len(), true);
+            self.validity = Some(validity);
         }
         if let Some(x) = self.validity.as_mut() {
             x.set(index, value.is_some())
diff --git a/src/bitmap/immutable.rs b/src/bitmap/immutable.rs
index a6a3a70b2e..dccc52bdd6 100644
--- a/src/bitmap/immutable.rs
+++ b/src/bitmap/immutable.rs
@@ -26,7 +26,8 @@ pub struct Bitmap {
 
 impl std::fmt::Debug for Bitmap {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        fmt(&self.bytes, self.offset, self.length, f)
+        let (bytes, offset, len) = self.as_slice();
+        fmt(bytes, offset, len, f)
     }
 }
 
@@ -111,8 +112,8 @@ impl Bitmap {
     /// exceeds the allocated capacity of `self`.
     #[inline]
     pub fn slice(mut self, offset: usize, length: usize) -> Self {
+        assert!(offset + length <= self.length);
         self.offset += offset;
-        assert!(self.offset + length <= self.bytes.len() * 8);
         self.length = length;
         self.null_count = null_count(&self.bytes, self.offset, self.length);
         self
diff --git a/src/bitmap/utils/slice_iterator.rs b/src/bitmap/utils/slice_iterator.rs
index 686c5f1c16..c081a79198 100644
--- a/src/bitmap/utils/slice_iterator.rs
+++ b/src/bitmap/utils/slice_iterator.rs
@@ -87,7 +87,7 @@ impl<'a> Iterator for SlicesIterator<'a> {
                 // at the beginning of a byte => try to skip it all together
                 match (self.on_region, self.current_byte) {
                     (true, &255u8) => {
-                        self.len += 8;
+                        self.len = std::cmp::min(self.max_len - self.start, self.len + 8);
                         match self.values.next() {
                             Some(v) => self.current_byte = v,
                             None => return self.finish(),
@@ -95,7 +95,7 @@ impl<'a> Iterator for SlicesIterator<'a> {
                         continue;
                     }
                     (false, &0) => {
-                        self.len += 8;
+                        self.len = std::cmp::min(self.max_len - self.start, self.len + 8);
                         match self.values.next() {
                             Some(v) => self.current_byte = v,
                             None => return self.finish(),


Test patch:
diff --git a/tests/it/array/primitive/mutable.rs b/tests/it/array/primitive/mutable.rs
index 8dbff29823..0adb4a534d 100644
--- a/tests/it/array/primitive/mutable.rs
+++ b/tests/it/array/primitive/mutable.rs
@@ -2,19 +2,60 @@ use arrow2::{
     array::*,
     bitmap::{Bitmap, MutableBitmap},
     buffer::MutableBuffer,
+    datatypes::DataType,
 };
 use std::iter::FromIterator;
 
+#[test]
+fn from_and_into_data() {
+    let a = MutablePrimitiveArray::from_data(
+        DataType::Int32,
+        MutableBuffer::from([1i32, 0]),
+        Some(MutableBitmap::from([true, false])),
+    );
+    assert_eq!(a.len(), 2);
+    let (a, b, c) = a.into_data();
+    assert_eq!(a, DataType::Int32);
+    assert_eq!(b, MutableBuffer::from([1i32, 0]));
+    assert_eq!(c, Some(MutableBitmap::from([true, false])));
+}
+
+#[test]
+fn to() {
+    let a = MutablePrimitiveArray::from_data(
+        DataType::Int32,
+        MutableBuffer::from([1i32, 0]),
+        Some(MutableBitmap::from([true, false])),
+    );
+    let a = a.to(DataType::Date32);
+    assert_eq!(a.data_type(), &DataType::Date32);
+}
+
+#[test]
+fn values_mut_slice() {
+    let mut a = MutablePrimitiveArray::from_data(
+        DataType::Int32,
+        MutableBuffer::from([1i32, 0]),
+        Some(MutableBitmap::from([true, false])),
+    );
+    let values = a.values_mut_slice();
+
+    values[0] = 10;
+    assert_eq!(a.values()[0], 10);
+}
+
 #[test]
 fn push() {
     let mut a = MutablePrimitiveArray::<i32>::new();
     a.push(Some(1));
     a.push(None);
-    assert_eq!(a.len(), 2);
+    a.push_null();
+    assert_eq!(a.len(), 3);
     assert!(a.is_valid(0));
     assert!(!a.is_valid(1));
+    assert!(!a.is_valid(2));
 
-    assert_eq!(a.values(), &MutableBuffer::from([1, 0]));
+    assert_eq!(a.values(), &MutableBuffer::from([1, 0, 0]));
 }
 
 #[test]
@@ -29,6 +70,17 @@ fn set() {
     assert!(a.is_valid(1));
 
     assert_eq!(a.values(), &MutableBuffer::from([2, 1]));
+
+    let mut a = MutablePrimitiveArray::<i32>::from_slice([1, 2]);
+
+    a.set(0, Some(2));
+    a.set(1, None);
+
+    assert_eq!(a.len(), 2);
+    assert!(a.is_valid(0));
+    assert!(!a.is_valid(1));
+
+    assert_eq!(a.values(), &MutableBuffer::from([2, 0]));
 }
 
 #[test]
@@ -72,3 +124,19 @@ fn extend_trusted_len() {
     );
     assert_eq!(a.values(), &MutableBuffer::<i32>::from([1, 2, 0, 4]));
 }
+
+#[test]
+fn set_validity() {
+    let mut a = MutablePrimitiveArray::<i32>::new();
+    a.extend_trusted_len(vec![Some(1), Some(2)].into_iter());
+    assert_eq!(a.validity(), &None);
+    a.set_validity(Some(MutableBitmap::from([false, true])));
+    assert_eq!(a.validity(), &Some(MutableBitmap::from([false, true])));
+}
+
+#[test]
+fn set_values() {
+    let mut a = MutablePrimitiveArray::<i32>::from_slice([1, 2]);
+    a.set_values(MutableBuffer::from([1, 3]));
+    assert_eq!(a.values().as_slice(), [1, 3]);
+}
diff --git a/tests/it/bitmap/utils/slice_iterator.rs b/tests/it/bitmap/utils/slice_iterator.rs
index 47bfcf2fbd..ea60940c41 100644
--- a/tests/it/bitmap/utils/slice_iterator.rs
+++ b/tests/it/bitmap/utils/slice_iterator.rs
@@ -1,144 +1,169 @@
+use rand::distributions::{Bernoulli, Uniform};
+use rand::prelude::StdRng;
+use rand::Rng;
+use rand::SeedableRng;
+
 use arrow2::bitmap::utils::SlicesIterator;
 use arrow2::bitmap::Bitmap;
 
-#[cfg(test)]
-mod tests {
-    use super::*;
-
-    #[test]
-    fn check_invariant() {
-        let values = (0..8).map(|i| i % 2 != 0).collect::<Bitmap>();
-        let iter = SlicesIterator::new(&values);
+#[test]
+fn check_invariant() {
+    let values = (0..8).map(|i| i % 2 != 0).collect::<Bitmap>();
+    let iter = SlicesIterator::new(&values);
 
-        let slots = iter.slots();
+    let slots = iter.slots();
 
-        let slices = iter.collect::<Vec<_>>();
+    let slices = iter.collect::<Vec<_>>();
 
-        assert_eq!(slices, vec![(1, 1), (3, 1), (5, 1), (7, 1)]);
+    assert_eq!(slices, vec![(1, 1), (3, 1), (5, 1), (7, 1)]);
 
-        let mut sum = 0;
-        for (_, len) in slices {
-            sum += len;
-        }
-        assert_eq!(sum, slots);
+    let mut sum = 0;
+    for (_, len) in slices {
+        sum += len;
     }
+    assert_eq!(sum, slots);
+}
 
-    #[test]
-    fn single_set() {
-        let values = (0..16).map(|i| i == 1).collect::<Bitmap>();
+#[test]
+fn single_set() {
+    let values = (0..16).map(|i| i == 1).collect::<Bitmap>();
 
-        let iter = SlicesIterator::new(&values);
-        let count = iter.slots();
-        let chunks = iter.collect::<Vec<_>>();
+    let iter = SlicesIterator::new(&values);
+    let count = iter.slots();
+    let chunks = iter.collect::<Vec<_>>();
 
-        assert_eq!(chunks, vec![(1, 1)]);
-        assert_eq!(count, 1);
-    }
+    assert_eq!(chunks, vec![(1, 1)]);
+    assert_eq!(count, 1);
+}
 
-    #[test]
-    fn single_unset() {
-        let values = (0..64).map(|i| i != 1).collect::<Bitmap>();
+#[test]
+fn single_unset() {
+    let values = (0..64).map(|i| i != 1).collect::<Bitmap>();
 
-        let iter = SlicesIterator::new(&values);
-        let count = iter.slots();
-        let chunks = iter.collect::<Vec<_>>();
+    let iter = SlicesIterator::new(&values);
+    let count = iter.slots();
+    let chunks = iter.collect::<Vec<_>>();
 
-        assert_eq!(chunks, vec![(0, 1), (2, 62)]);
-        assert_eq!(count, 64 - 1);
-    }
+    assert_eq!(chunks, vec![(0, 1), (2, 62)]);
+    assert_eq!(count, 64 - 1);
+}
 
-    #[test]
-    fn generic() {
-        let values = (0..130).map(|i| i % 62 != 0).collect::<Bitmap>();
+#[test]
+fn generic() {
+    let values = (0..130).map(|i| i % 62 != 0).collect::<Bitmap>();
 
-        let iter = SlicesIterator::new(&values);
-        let count = iter.slots();
-        let chunks = iter.collect::<Vec<_>>();
+    let iter = SlicesIterator::new(&values);
+    let count = iter.slots();
+    let chunks = iter.collect::<Vec<_>>();
 
-        assert_eq!(chunks, vec![(1, 61), (63, 61), (125, 5)]);
-        assert_eq!(count, 61 + 61 + 5);
-    }
+    assert_eq!(chunks, vec![(1, 61), (63, 61), (125, 5)]);
+    assert_eq!(count, 61 + 61 + 5);
+}
 
-    #[test]
-    fn incomplete_byte() {
-        let values = (0..6).map(|i| i == 1).collect::<Bitmap>();
+#[test]
+fn incomplete_byte() {
+    let values = (0..6).map(|i| i == 1).collect::<Bitmap>();
 
-        let iter = SlicesIterator::new(&values);
-        let count = iter.slots();
-        let chunks = iter.collect::<Vec<_>>();
+    let iter = SlicesIterator::new(&values);
+    let count = iter.slots();
+    let chunks = iter.collect::<Vec<_>>();
 
-        assert_eq!(chunks, vec![(1, 1)]);
-        assert_eq!(count, 1);
-    }
+    assert_eq!(chunks, vec![(1, 1)]);
+    assert_eq!(count, 1);
+}
 
-    #[test]
-    fn incomplete_byte1() {
-        let values = (0..12).map(|i| i == 9).collect::<Bitmap>();
+#[test]
+fn incomplete_byte1() {
+    let values = (0..12).map(|i| i == 9).collect::<Bitmap>();
 
-        let iter = SlicesIterator::new(&values);
-        let count = iter.slots();
-        let chunks = iter.collect::<Vec<_>>();
+    let iter = SlicesIterator::new(&values);
+    let count = iter.slots();
+    let chunks = iter.collect::<Vec<_>>();
 
-        assert_eq!(chunks, vec![(9, 1)]);
-        assert_eq!(count, 1);
-    }
+    assert_eq!(chunks, vec![(9, 1)]);
+    assert_eq!(count, 1);
+}
 
-    #[test]
-    fn end_of_byte() {
-        let values = (0..16).map(|i| i != 7).collect::<Bitmap>();
+#[test]
+fn end_of_byte() {
+    let values = (0..16).map(|i| i != 7).collect::<Bitmap>();
 
-        let iter = SlicesIterator::new(&values);
-        let count = iter.slots();
-        let chunks = iter.collect::<Vec<_>>();
+    let iter = SlicesIterator::new(&values);
+    let count = iter.slots();
+    let chunks = iter.collect::<Vec<_>>();
 
-        assert_eq!(chunks, vec![(0, 7), (8, 8)]);
-        assert_eq!(count, 15);
-    }
+    assert_eq!(chunks, vec![(0, 7), (8, 8)]);
+    assert_eq!(count, 15);
+}
 
-    #[test]
-    fn bla() {
-        let values = vec![true, true, true, true, true, true, true, false]
-            .into_iter()
-            .collect::<Bitmap>();
-        let iter = SlicesIterator::new(&values);
-        let count = iter.slots();
-        assert_eq!(values.null_count() + iter.slots(), values.len());
+#[test]
+fn bla() {
+    let values = vec![true, true, true, true, true, true, true, false]
+        .into_iter()
+        .collect::<Bitmap>();
+    let iter = SlicesIterator::new(&values);
+    let count = iter.slots();
+    assert_eq!(values.null_count() + iter.slots(), values.len());
 
-        let total = iter.into_iter().fold(0, |acc, x| acc + x.1);
+    let total = iter.into_iter().fold(0, |acc, x| acc + x.1);
 
-        assert_eq!(count, total);
-    }
+    assert_eq!(count, total);
+}
 
-    #[test]
-    fn past_end_should_not_be_returned() {
-        let values = Bitmap::from_u8_slice(&[0b11111010], 3);
-        let iter = SlicesIterator::new(&values);
-        let count = iter.slots();
-        assert_eq!(values.null_count() + iter.slots(), values.len());
+#[test]
+fn past_end_should_not_be_returned() {
+    let values = Bitmap::from_u8_slice(&[0b11111010], 3);
+    let iter = SlicesIterator::new(&values);
+    let count = iter.slots();
+    assert_eq!(values.null_count() + iter.slots(), values.len());
 
-        let total = iter.into_iter().fold(0, |acc, x| acc + x.1);
+    let total = iter.into_iter().fold(0, |acc, x| acc + x.1);
 
-        assert_eq!(count, total);
-    }
+    assert_eq!(count, total);
+}
 
-    #[test]
-    fn sliced() {
-        let values = Bitmap::from_u8_slice(&[0b11111010, 0b11111011], 16);
-        let values = values.slice(8, 2);
-        let iter = SlicesIterator::new(&values);
+#[test]
+fn sliced() {
+    let values = Bitmap::from_u8_slice(&[0b11111010, 0b11111011], 16);
+    let values = values.slice(8, 2);
+    let iter = SlicesIterator::new(&values);
 
-        let chunks = iter.collect::<Vec<_>>();
+    let chunks = iter.collect::<Vec<_>>();
 
-        // the first "11" in the second byte
-        assert_eq!(chunks, vec![(0, 2)]);
-    }
+    // the first "11" in the second byte
+    assert_eq!(chunks, vec![(0, 2)]);
+}
+
+#[test]
+fn remainder_1() {
+    let values = Bitmap::from_u8_slice(&[0, 0, 0b00000000, 0b00010101], 27);
+    let values = values.slice(22, 5);
+    let iter = SlicesIterator::new(&values);
+    let chunks = iter.collect::<Vec<_>>();
+    assert_eq!(chunks, vec![(2, 1), (4, 1)]);
+}
 
-    #[test]
-    fn remainder_1() {
-        let values = Bitmap::from_u8_slice(&[0, 0, 0b00000000, 0b00010101], 27);
-        let values = values.slice(22, 5);
-        let iter = SlicesIterator::new(&values);
-        let chunks = iter.collect::<Vec<_>>();
-        assert_eq!(chunks, vec![(2, 1), (4, 1)]);
+#[test]
+fn filter_slices() {
+    let mut rng = StdRng::seed_from_u64(42);
+    let length = 500;
+
+    let mask: Bitmap = (0..length)
+        .map(|_| {
+            let v: bool = (&mut rng).sample(Bernoulli::new(0.5).unwrap());
+            v
+        })
+        .collect();
+
+    for offset in 100usize..(length - 1) {
+        let len = (&mut rng).sample(Uniform::new(0, length - offset));
+        let mask_s = mask.clone().slice(offset, len);
+
+        let iter = SlicesIterator::new(&mask_s);
+        iter.for_each(|(start, slice_len)| {
+            if start + slice_len > len {
+                panic!("Fail")
+            }
+        });
     }
 }