Resolve into_shape() limitations

[jturner314]

The .into_shape() method works in some cases, but compared to NumPy's reshape() has the following limitations:

1. It only works for arrays with contiguous memory layout.
2. The result depends on the layout of the data in memory. (Calling .into_shape() on an array with Fortran memory layout will give a different result from calling .into_shape() on the logically equivalent array with C memory layout.)
3. All of the new axis lengths need to be known. (NumPy has the nice ability to use -1 to indicate that an axis length should be inferred.)

I'd like to add a method or methods to resolve at least limitations 1 and 2.

In order to handle arrays without contiguous memory layout, the data needs to be cloned in some cases. If the input array owns its data, this is simple – just return a new owned array. However, if the input array is an ArrayView, then you need to return something like Cow. If the input array is an ArrayViewMut, you need some way to return a mutable view with the correct shape but make sure that any changes to that view are copied back to the original underlying data.

A prototype of one approach is at jturner314/ndarray@0157df8. This introduces a few new types, including ArrayViewTemp which handles the temporary array if the input is an ArrayView, and ArrayViewMutTemp, which handles the case where the input is an ArrayViewMut (using Drop to make sure the data is written from the temporary array back to the original underlying data).

It's worth noting that this type of problem (needing a temporary array in some cases) also occurs for operations other than reshaping. For example, I'm working on a similar approach for ndarray-linalg to convert arrays/views to Fortran layout to pass to LAPACK. If something like ArrayViewTemp and ArrayViewMutTemp get added to ndarray, I can reuse those types in ndarray-linalg for the changing-layout problem.

What do you think?

Edit: After thinking about this a little more, I realized:

1. Instead of wrapping arrays in ArrayViewTemp and ArrayViewMutTemp enums, it would be cleaner to create new reprs for the S type parameter in ArrayBase that implement Data/DataMut.
2. It might be possible for drop_hook in ArrayViewMutTempRepr to own the view of the original data so that the view field and Do type parameter could be removed.

[bluss]

The drawback 2 seems critically bad, but at the same time, it's in the interest of not biasing too much in favour of the default c order.

[jturner314]

The drawback 2 seems critically bad, but at the same time, it's in the interest of not biasing too much in favour of the default c order.

The issue is that in a large program, it can be difficult to determine the memory layout of an array by just reading the source code, so the result of .into_shape() is fairly unpredictable. For example, slicing often creates custom-layout views, and I typically create column-major arrays for use with ndarray-linalg (for efficiency when calling LAPACK routines). The memory layout of the result of some methods isn't even specified in the documentation (e.g. .dot()). Every time before I call .into_shape(), I have to check if the memory layout is what I think it is and explicitly copy the data into a new row-/column-major array if it isn't.

I really like the way NumPy's reshape() handles this. It takes a parameter order for the desired logical interpretation of the reshaping operation. If order='C', then the data is reshaped following row-major order; if order='F', then the data is reshaped following column-major order; and if order='A', then the ordering is chosen based on the memory layout of the array (similar to the existing .into_shape()). The 'C' and 'F' options are completely independent of the underlying memory layout of the array; they dictate the logical interpretation of the reshape() operation, similar to how indices in ndarray are logically row-major even if the underlying memory layout is column-major or some custom layout.

The challenge with directly applying NumPy's reshape() to ndarray is that in some cases, the result can just be a view of the original array, while in other cases, the data actually needs to be copied. For owned arrays, it's simple – just take ownership of the array and return a new owned array (copying if necessary.) This doesn't work for views, though. Personally, I think the best approach for views is to add new types for the S parameter in ArrayBase. For read-only views, this would be something like:

enum TmpViewRepr<'a, A> {
    View(ViewRepr<&'a A>),
    Temporary(OwnedRepr<A>),
}

impl<'a, A> Data for TmpViewRepr<'a, A> {
    // ...
}

which can represent a read-only view of the data or a temporary copy. (This could also be called CowRepr if you want clone-on-write functionality.) The other type would be something like

enum TmpViewMutRepr<'a, A> {
    View(ViewRepr<&'a mut A>),
    Temporary {
        tmp: OwnedRepr<A>,
        drop_hook: Box<FnMut(&mut Self)>
    },
}

impl<'a, A> Data for TmpViewMutRepr<'a, A> {
    // ...
}

impl<'a, A> DataMut for TmpViewMutRepr<'a, A> {
    // ...
}

which can represent a mutable view of the data or a temporary copy. When this type gets dropped, if it's the Temporary variant, it would call drop_hook, which could be used to write the modified data in the temporary copy back to the original array. (The drop_hook could be a closure with a reference to the original array.)

These types are useful not only for improving .into_shape() in ndarray but also for client code. In my own programs, I sometimes need to either view existing data or create a temporary array, which could be handled by TmpViewRepr. In ndarray-linalg, these types would be useful when changing the memory layout of arrays to pass to LAPACK routines.

What do you think?

Edit: Yet another place where TmpViewMutRepr would be useful is if a function needs &mut [A] as an argument, but you only have an ArrayViewMut1<A> which might not be contiguous. You could do .into_contiguous().as_slice_mut().unwrap(), where .into_contiguous() would return an ArrayBase<S::TmpRepr, D> where ViewRepr<&'a mut A>::TmpRepr = TmpViewMutRepr<'a, A>.

[bluss]

Just a brief note, I'm sorry; I've been swamped this week. RcArray is much more like numpy's array :-P But in the end we went for the tempting Rust model of Array vs views.

So a solution RcArray could also be an option; note that your "Temp" should probably be called Cow.

[jturner314]

Now that #632 is merged, we can add an .as_shape() method.

I think we should require a logical order parameter (similar to NumPy's .reshape()). For example, the user might write

// row-major order
arr.as_shape((3, 4), Order::RowMajor)?
// column-major order
arr.as_shape((3, 4), Order::ColMajor)?

and the API would be

/// This is analogous to the `order` parameter in
/// [`numpy.reshape()`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.reshape.html#numpy.reshape).
pub enum Order {
    /// C-like order
    RowMajor,
    /// Fortran-like order
    ColMajor,
    #[doc(hidden)]
    __NonExhaustive,
}

impl<A, S, D> ArrayBase<S, D>
where
    S: RawData<Elem = A>,
    D: Dimension,
{
    pub fn into_shape<E>(self, shape: E, order: Order) -> Result<ArrayBase<S, E::Dim>, ShapeError>
    where
        S: DataOwned,
        E: IntoDimension,
    {
    }

    pub fn as_shape<E>(&self, shape: E, order: Order) -> Result<CowArray<'_, A, E::Dim>, ShapeError>
    where
        S: Data,
        E: IntoDimension,
    {
    }
}

We could add other variants to Order, e.g. Automatic (like NumPy's 'A') or Custom(D) (for arbitrary axis order).

Edit: Earlier, I included a second approach, but I later realized that it didn't actually work, so I've removed it from this comment.

Thoughts?

[bluss]

Yes, implementing @jturner314's plan here is important. We shouldn't just add a new method but need to rethink how to handle all of reshape, into_shape and the new method.

The as_ name doesn't sound like it fits as well as the into_ one.. Maybe to_ if it can't be into_?

[bluss]

as_shape or to_shape (depending on name) has been straightforward to implement, but for into_shape I'm not sure what design to choose.

I think an into_shape method similar to the existing one is needed - one that works for any array, even if it's a raw view or view and even if it has an element type without Clone. With those restrictions, into_shape can't do much more than what it does today, except to use an order parameter to further limit which cases it will be succesful. But maybe the existing into_shape can be given a different name, to make room for a better into_shape ?

(Edit - is it possible to find a way for into_shape to serve both purposes - both reshaping views and then more functionality for owned arrays?)

[jturner314]

Regarding the name of as_shape/to_shape, I just remembered that we have as_standard_layout, which returns a CowArray. It would be nice for these two similar methods to be named consistently. I do think you're right that to_shape is probably the better name, since as_ implies that the conversion is always cheap. (That's what Rust API Guidelines currently recommend, too.) If we do eventually add something like the ArrayViewMutTemp type I proposed in the first comment on this issue, I suppose the mutable version would be called to_shape_mut.

Regarding .into_shape(), we could have different behavior and requirements for the different storage types. (Owned types could require A: Clone and clone if necessary; view types would error if cloning would be necessary.) However, I suspect that would be too confusing.

I think I'd prefer to have two separate methods. into_shape and reshape seem like pretty good names.

// Clones elements if necessary.
fn into_shape<E>(self, shape: E, order: Order) -> Result<ArrayBase<S, E::Dim>, ShapeError>
where
    A: Clone,
    S: DataOwned,
    E: IntoDimension,
{}

// Errors if cloning would be necessary.
fn reshape<E>(self, shape: E, order: Order) -> Result<ArrayBase<S, E::Dim>, ShapeError>
where
    E: IntoDimension,
{}

(Or the names could be swapped. I'm not sure which method is better to call which name.)

Calls to the existing reshape method for ArcArray would be replaced by .clone().into_shape().

[bluss]

By implementing a by-value iterator for Array and inserting some "reflection" methods into RawData (that can "upgrade" to DataOwned dynamically if possible), then it's possible for something like reshape to work for both raw view and be extended to handle any reshaping of a Array. However, this technique doesn't work for ArcArray because there is nothing that can make us discover if the element has the needed Clone bound or not (which is needed for CoW).

I'm also looking at builder-type solutions because I think having no default value for the order is very noisy. Having a builder would make it possible to have RowMajor be the default value.

A (less than?) nice trick is that the builder can have a method .unwrap() which means that .into_shape((a, b)).unwrap() could continue to work. It's hacky

a.into_shape(x).unwrap(); // unwrap the builder to an array - default order is RowMajor
a.into_shape(y).order(Order::ColumnMajor).unwrap(); // override default order
a.into_shape(z).result(); // Get the Result<ArrayBase<_>, _> value

[jturner314]

... I think having no default value for the order is very noisy. Having a builder would make it possible to have RowMajor be the default value.

I actually disagree with this. For most methods (e.g. the constructors) it makes sense to have a default layout/order because the layout doesn't affect the visible results (i.e. the element values). For reshaping though, the order does affect the visible results, so I think it's worthwhile to require an order parameter. Requiring it also encourages the user think carefully about what the reshaping means. (Reshaping can be a confusing operation.) I'm not strongly opposed to making it optional, but IMO the better design is to require it.

[nemosupremo]

Might be a bit irrelevant for the thread, but I didn't think this warranted it's own issue. With regards to limitation 3, I believe you can't "infer" the correct shape because dimensions are of type usize. I think there are a couple ways to fix this without rewriting the entire API (and also keeping usize for internal dimensions). You could have a function, defined on the Dimension trait like a.raw_dim().reshape(1,2,3,-1) so that into_shape would be:

a.into_shape(a.raw_dim().reshape(1,2,3,-1))

Would this be an addition that would be approved in the ndarray api?

Edit:

I guess you are 50* of the way there with something like:

a.into_shape(a.raw_dim().reshape(1,2,3,a.raw_dim().as_array_view().product()/(1*2*3)))

`

[bluss]

and a.raw_dim().as_array_view().product() is the same as a.len() so it was never so far away, I guess? Isn't this just the same thing?

let new_shape = (1, 2, 3, a.len()/(1 * 2 * 3));
a.into_shape(new_shape)

Edit: There are some in-band and quite wonky alternatives for a placeholder - instead of -1 for usize we have either 0 or !0 - zero could have a "double duty" and if the input array is of non-zero size, we replace it by the appropriate rest of the dimension - if the input array is of zero size than preserving the zero and replacing it by the rest is the same thing, which is nice.

!0 also spelled usize::MAX can also be a placeholder since it has no use as an actual axis length.

That would look like this:

a.into_shape((1, 2, 0, 3)).unwrap()  // reshape to 1 x 2 x rest x 3
a.into_shape((1, 2, usize::MAX, 3)).unwrap()  // reshape to 1 x 2 x rest x 3

[bluss]

@jturner314 It affects the visible results, but it is just a logical order default - and we have that same default across a lot of API, so it would not be out of place here. I would be happy to just have the parameter for an order - that makes the implementation job easier in our crate, less work and less complexity with a builder. But I think having a default and allowing it to be overridden is the best for the common case and is easier to use, and will cause less breakage for users.

[bluss]

Instead of a builder, it's possible the argument should just be builder like instead. Just like it's done for constructors in fact - a shape and an optional order parameter. .into_shape((2, 2, 2)) or .into_shape((2, 2, 2).order(Order::RowMajor)) or similar?

Potentially - but it would be messy compared with existing methods - using traits for "overloading" in a different way and accepting both shape and (shape, order) as a single function parameter. Same effect by different mechanism.

[emk]

Thank you to everyone working on shape transformations!

Here is an implementation of try_to_shape_mut which passes via as_slice_mut (and is therefore fallible). I use this to reshape neural net parameters, either to flatten them for the optimizer, or to deal with all the fun shapes inside convolutional layers.

let mut a = arr1(&[1, 2, 3, 4, 5, 6]);
let b = a.try_to_shape_mut((3, 2)).unwrap();
assert_eq!(b, arr2(&[[1, 2], [3, 4], [5, 6]]));

The full code is here:

Implemetation of `try_to_shape_mut`

The unit tests below were written almost entirely by Copilot, which impressed me.

/// Helper trait for reshaping `ndarray` arrays mutably. See [issue #390][] for
/// more details on upstream support for this.
///
/// [issue #390]: https://github.com/rust-ndarray/ndarray/issues/390
pub trait TryToShapeMut<'a, Elem> {
    /// Attempt to reshape a mutable `ndarray` array. This is basically
    /// the same as `ArrayBase::to_shape` but for mutable arrays. It will fail
    /// if the array is not contiguous in memory.
    fn try_to_shape_mut<Shape>(
        &'a mut self,
        new_shape: Shape,
    ) -> Result<ArrayViewMut<'a, Elem, Shape::Dim>, ShapeError>
    where
        Shape: ShapeArg + Into<StrideShape<Shape::Dim>>;
}

impl<'a, Elem, A, D> TryToShapeMut<'a, Elem> for ArrayBase<A, D>
where
    A: DataMut<Elem = Elem>,
    D: Dimension,
{
    fn try_to_shape_mut<Shape>(
        &'a mut self,
        new_shape: Shape,
    ) -> Result<ArrayViewMut<'a, Elem, Shape::Dim>, ShapeError>
    where
        Shape: ShapeArg + Into<StrideShape<Shape::Dim>>,
    {
        let slice_mut = self
            .as_slice_mut()
            .ok_or_else(|| ShapeError::from_kind(ErrorKind::IncompatibleLayout))?;
        ArrayViewMut::from_shape(new_shape.into(), slice_mut)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use ndarray::{arr1, arr2, arr3};

    #[test]
    fn test_1d() {
        let mut a = arr1(&[1, 2, 3, 4, 5, 6]);
        let b = a.try_to_shape_mut((3, 2)).unwrap();
        assert_eq!(b, arr2(&[[1, 2], [3, 4], [5, 6]]));
    }

    #[test]
    fn test_2d() {
        let mut a = arr2(&[[1, 2, 3], [4, 5, 6]]);
        let b = a.try_to_shape_mut((3, 2)).unwrap();
        assert_eq!(b, arr2(&[[1, 2], [3, 4], [5, 6]]));
    }

    #[test]
    fn test_3d() {
        let mut a = arr3(&[[[1, 2], [3, 4]], [[5, 6], [7, 8]]]);
        let b = a.try_to_shape_mut((4, 2)).unwrap();
        assert_eq!(b, arr2(&[[1, 2], [3, 4], [5, 6], [7, 8]]));
    }

    #[test]
    fn test_3d_fail() {
        let mut a = arr3(&[[[1, 2], [3, 4]], [[5, 6], [7, 8]]]);
        let b = a.try_to_shape_mut((4, 3));
        assert!(b.is_err());
    }

    #[test]
    fn reshape_view_mut() {
        let mut a = arr2(&[[1, 2, 3], [4, 5, 6]]);
        let mut v = a.view_mut();
        let b = v.try_to_shape_mut((3, 2)).unwrap();
        assert_eq!(b, arr2(&[[1, 2], [3, 4], [5, 6]]));
    }
}

[bluss]

.into_shape() is deprecated in the next release - 0.16.0, so that resolves this bug. Users are now directed to .to_shape() (0.15 and later) and .into_shape_with_order, .into_shape_clone (0.16 and later).

Fixed by #1310