Repository: rust-ndarray/ndarray
Pull request #1297 (2023-06-17 23:12:42)

Updated Windows `base` Computations to be Safer
Please refer to #1249 for context and discussions, specifically [this comment](https://github.com/rust-ndarray/ndarray/pull/1249#issuecomment-1595677103).

The assertion verifying a window's size dimension or axis' stride is non-zero has been removed and outsourced to `Slice`, which will error when:
1. `end` > `ax_desc.len`, which can only happen when `wsz == 0`
2. `step == 0`, which can only happen when an axis' stride is zero

Thus, we maintain the same functionality as before

nilgoyette: > Here we'll have panics (debug mode) due to wraparound immediately if the user passes in any array with inverted axis (negative stride)

I don't want to ask too much of a generous contributor, but if you can, could you please add a test that would have failed before the fix in this PR? (a test with negative strides)
LazaroHurtado: > could you please add a test that would have failed before the fix in this PR? (a test with negative strides)

No worries! But I am not totally sure if this is possible, `windows_with_stride`  requires `stride` to implement `IntoDimension<Dim = D>` which already restricts each axis to be non-negative (`type Ix = usize;`). If I'm overlooking something please let me know
nilgoyette: If it's impossible to pass an array with negative strides, then I don't understand the point of this PR.

Can't you call `windows` on a transposed matrix?

    m.t().windows(...)

If I understand bluss comment correctly, it should create negative strides.
LazaroHurtado: Ah sorry there are two strides here, the parameter and the offset, I was thinking about the parameter. I believe there's already a `windows` test that creates a matrix with negative strides by inverting it [here](https://github.com/rust-ndarray/ndarray/blob/17a8d25294d33e0f562af948434dbb284647872b/tests/windows.rs#L271) but I can create a new test for both `windows` and `windows_with_stride` that acts on a transposed matrix as you suggested
bluss: > If I understand bluss comment correctly, it should create negative strides.

Transpose just changes order of axes, it doesn't modify their lengths or strides. "Axis 0 and 1 become axis 1 and 0".

Use instead ndarray's method [`.invert_axis(Axis(0))`](https://docs.rs/ndarray/latest/ndarray/struct.ArrayBase.html#method.invert_axis), that will reverse the matrix along that axis

Example on matrix with dimensions (n1, n2) and strides (s1, s2):

- (n1, n2) and (s1, s2) -- transpose -> (n2, n1) and (s2, s1)
- (n1, n2) and (s1, s2) -- invert axis 0 -> (n1, n2)  and (-s1, s2)
bluss: > I don't want to ask too much of a generous contributor, but if you can, could you please add a test that would have failed before the fix in this PR? (a test with negative strides)

I agree with this one.

@LazaroHurtado  We need a negative axis input array. The window strides (your feature) still just needs to be anything that's not just (1, 1, 1), for example something with a stride of 2.

Patch:
diff --git a/src/iterators/windows.rs b/src/iterators/windows.rs
index d84b0e7b..6238d0ed 100644
--- a/src/iterators/windows.rs
+++ b/src/iterators/windows.rs
@@ -3,6 +3,7 @@ use crate::imp_prelude::*;
 use crate::IntoDimension;
 use crate::Layout;
 use crate::NdProducer;
+use crate::Slice;
 
 /// Window producer and iterable
 ///
@@ -24,16 +25,19 @@ impl<'a, A, D: Dimension> Windows<'a, A, D> {
 
         let mut unit_stride = D::zeros(ndim);
         unit_stride.slice_mut().fill(1);
-        
+
         Windows::new_with_stride(a, window, unit_stride)
     }
 
-    pub(crate) fn new_with_stride<E>(a: ArrayView<'a, A, D>, window_size: E, strides: E) -> Self
+    pub(crate) fn new_with_stride<E>(a: ArrayView<'a, A, D>, window_size: E, axis_strides: E) -> Self
     where
         E: IntoDimension<Dim = D>,
     {
         let window = window_size.into_dimension();
-        let strides_d = strides.into_dimension();
+
+        let strides = axis_strides.into_dimension();
+        let window_strides = a.strides.clone();
+
         ndassert!(
             a.ndim() == window.ndim(),
             concat!(
@@ -44,45 +48,35 @@ impl<'a, A, D: Dimension> Windows<'a, A, D> {
             a.ndim(),
             a.shape()
         );
+
         ndassert!(
-            a.ndim() == strides_d.ndim(),
+            a.ndim() == strides.ndim(),
             concat!(
                 "Stride dimension {} does not match array dimension {} ",
                 "(with array of shape {:?})"
             ),
-            strides_d.ndim(),
+            strides.ndim(),
             a.ndim(),
             a.shape()
         );
-        let mut size = a.dim;
-        for ((sz, &ws), &stride) in size
-            .slice_mut()
-            .iter_mut()
-            .zip(window.slice())
-            .zip(strides_d.slice())
-        {
-            assert_ne!(ws, 0, "window-size must not be zero!");
-            assert_ne!(stride, 0, "stride cannot have a dimension as zero!");
-            // cannot use std::cmp::max(0, ..) since arithmetic underflow panics
-            *sz = if *sz < ws {
-                0
-            } else {
-                ((*sz - (ws - 1) - 1) / stride) + 1
-            };
-        }
-        let window_strides = a.strides.clone();
 
-        let mut array_strides = a.strides.clone();
-        for (arr_stride, ix_stride) in array_strides.slice_mut().iter_mut().zip(strides_d.slice()) {
-            *arr_stride *= ix_stride;
-        }
+        let mut base = a;
+        base.slice_each_axis_inplace(|ax_desc| {
+            let len = ax_desc.len;
+            let wsz = window[ax_desc.axis.index()];
+            let stride = strides[ax_desc.axis.index()];
 
-        unsafe {
-            Windows {
-                base: ArrayView::new(a.ptr, size, array_strides),
-                window,
-                strides: window_strides,
+            if len < wsz {
+                Slice::new(0, Some(0), 1)
+            } else {
+                Slice::new(0, Some((len - wsz + 1) as isize), stride as isize)
             }
+        });
+
+        Windows {
+            base,
+            window,
+            strides: window_strides,
         }
     }
 }


Test patch:
diff --git a/tests/windows.rs b/tests/windows.rs
index 2c928aae..095976ea 100644
--- a/tests/windows.rs
+++ b/tests/windows.rs
@@ -302,3 +302,31 @@ fn test_window_neg_stride() {
         answer.iter()
     );
 }
+
+#[test]
+fn test_windows_with_stride_on_inverted_axis() {
+    let mut array = Array::from_iter(1..17).into_shape((4, 4)).unwrap();
+    
+    // inverting axis results in negative stride
+    array.invert_axis(Axis(0));
+    itertools::assert_equal(
+        array.windows_with_stride((2, 2), (2,2)),
+        vec![
+            arr2(&[[13, 14], [9, 10]]),
+            arr2(&[[15, 16], [11, 12]]),
+            arr2(&[[5, 6], [1, 2]]),
+            arr2(&[[7, 8], [3, 4]]),
+        ],
+    );
+
+    array.invert_axis(Axis(1));
+    itertools::assert_equal(
+        array.windows_with_stride((2, 2), (2,2)),
+        vec![
+            arr2(&[[16, 15], [12, 11]]),
+            arr2(&[[14, 13], [10, 9]]),
+            arr2(&[[8, 7], [4, 3]]),
+            arr2(&[[6, 5], [2, 1]]),
+        ],
+    );
+}
\ No newline at end of file