DataClone implementation for ViewRepr<&'a mut A>?

[LukeMathWalker]

I am writing a function in which I need to compute the first quartile without modifying the underlying array. I have thus tried to call clone on the array to get a copy but this stub

    fn example<S, T>(a: ArrayBase<S, Ix1>) -> [...]
    where
        S: Data<Elem=T>,
        T: Clone,
    {
        let first_quartile = a.clone().quantile_axis_mut(0.25, Axis(0));
        [...]
    }

will not compile:

    |
126 |         let first_quartile = a.clone().quantile_axis_mut(0.25, Axis(0));
    |                                ^^^^^
    |
    = note: the method `clone` exists but the following trait bounds were not satisfied:
            `ndarray::ArrayBase<S, ndarray::Dim<[usize; 1]>> : std::clone::Clone`

I have checked Clone implementation on ArrayBase (here) and it turns out that there is a bound on the Data associated type: it needs to implement the DataClone trait (here).

DataClone is implemented by all Data variants in ndarray apart from ViewRepr<&'a mut A> - why is that? Is there a deep reason or is it simply something that was never needed?

Edit: reading the finer details in the implementation of ViewRepr and DataClone it seems to me that implementing DataClone for ViewRepr<&'a mut A> might lead to multiple views on the same array with mut privilege - ViewRepr doesn't have access to the underlying data, hence we cannot duplicate it as we do for OwnedRepr, is my understanding correct?

[jturner314]

To clone all of the individual elements, you can use .to_owned() instead of .clone().

Calling .clone() on an ArrayView<'a, A, D> returns another ArrayView<'a, A, D>. If we allowed cloning ArrayViewMut<'a, A, D>, we'd violate Rust's aliasing rules.

You can think of ArrayView<'a, A, D> as being analogous to &'a A and ArrayViewMut<'a, A, D> as being analogous to &'a mut A. Rust's aliasing rules allow multiple simultaneous &'a A references to the same data, but prohibit a &'a mut A reference coexisting with any other references to the same data (&'a A or &'a mut A). Clone (and Copy) are implemented for &'a A in the standard library because it's legal to create a clone/copy of an immutable reference. Clone is not implemented for &'a mut A because that would allow creating multiple mutable references to the same data in safe code. Similarly, Clone is implemented for ArrayView<'a, A, D> but not ArrayViewMut<'a, A, D>.

[LukeMathWalker]

Ok, I guess I have it clear now - what probably tricked me is that this kind of code (on Rust Playground)

// A tuple struct with resources that implements the `Clone` trait
#[derive(Clone, Debug)]
struct Pair(Box<i32>, Box<i32>);

fn main() {
    // Instantiate `Pair`
    let mut pair = Pair(Box::new(1), Box::new(2));
    println!("original: {:?}", pair);
    let mut_ref_pair = &mut pair;
    println!("{:?}", mut_ref_pair.clone());
}

compiles and runs just fine. But I guess this is due to the fact that

mut_ref_pair.clone()

is actually desugared to

(*mut_ref_pair).clone()

thus relaying on the underlying implementation of Clone for Pair. Am I correct?

[jturner314]

Rust provides special handling for references which it doesn't provide for ArrayView[Mut].

The Clone trait is defined like this:

pub trait Clone {
    fn clone(&self) -> Self;
    // ... (clone_from)
}

Note, in particular, that the type of the parameter to clone is &Self.

When you call .clone() on T, Rust auto-refs the T to get a &T and then calls Clone::clone on that (edit: assuming T isn't &U where U: Clone). When you call .clone() on &T where T: Clone, Clone::clone is passed the &T directly (edit: this uses the Clone implementation for T). When you call .clone() on &mut Pair, I think the desugaring goes like this:

mut_ref_pair.clone()            // original
Clone::clone(&*mut_ref_pair)    // deref and then ref

but it may instead be

mut_ref_pair.clone()                   // original
Clone::clone(mut_ref_pair as &Pair)    // implicit coercion

I'm not entirely sure which. This description of Rust's auto-ref/deref rules seems to suggest the first version.

If we wanted to define a trait that's similar to the Clone trait but for arrays (using the analogy of ArrayView to &T), we could define:

pub trait ArrayClone {
    type View;
    fn array_clone(view: Self::View) -> Self;
    // ... (clone_from)
}

where View is the ArrayView type corresponding to Self, like &Self is the reference type corresponding to Self. However, since the argument is not self/&self/&mut self/self: Box<Self>, you couldn't call array_clone with dot notation, and since Rust doesn't automatically convert between owned arrays and views like it auto-derefs/refs references, you'd have to manually perform the necessary conversions yourself (if you didn't already have an ArrayView, you'd have to call .view() before calling ArrayClone::array_clone() on that).

Another related trait would be

pub trait ArrayClone {
    type Owned;
    fn array_clone(self) -> Self::Owned;
    // ... (clone_from)
}

which is similar, but note that this trait is implemented for the reference type, not the owned type. This is similar what I've proposed in #498 (which generalizes the .into_owned() method), except that #498 has the restriction that Self::Owned is always Array instead of possibly ArcArray.

[LukeMathWalker]

Thanks for the overview, this was really useful!

Speaking hypothetically, couldn't we reinforce the equivalence:

• T <=> Owned
• &T <=> View
• &mut T <=> ViewMut

by implementing Deref for immutable views and DerefMut for mutable views?

[jturner314]

I realized that a better analogy than "Array<A, D> is to ArrayViewMut<'a, A, D> as T is to &'a mut T" is "Array<A, D> is to ArrayViewMut<'a, A, D> as Vec<T> is to &'a mut [T]". Slices exhibit the same behavior as ArrayView/ArrayViewMut with regards to .clone():

let mut v = vec![3; 5];
{
    let s = &v[1..3];
    let _ = s.clone();
}
{
    let s = &mut v[1..3];
    // no method named `clone` found for type `&mut [{integer}]` in the current scope
    // let _ = s.clone();
}

Back to your question: I think it's instructive to first look at functions of the form

fn convert(t: &T) -> &U { ... }

in general. There are two primary ways to perform a conversion of this form:

1. Return a reference to one of the fields of t: &t.field.

2. Assuming the bitwise representations work out and no constraints are violated, it may be valid to perform a pointer cast followed by unsafe deref: unsafe { &*(t as *const T as *const U) }.

3. (A combination of 1 and 2, possibly also calling functions which also perform conversions via 1 or 2.)

Observe that the bitwise representation of U must always be a contiguous subset of the bitwise representation of T. This is also clear because &T and &U are effectively just pointers. In other words, U can't contain any bits that aren't in T.

But wait! That isn't true! What about slicing Vec<T> with a Range (&v[1..3])? Slicing a Vec with this notation is performed with the Index trait, which has a function index that is of a similar form as convert:

pub trait Index<Idx>
where
    Idx: ?Sized,
{
    type Output: ?Sized;
    fn index(&self, index: Idx) -> &Self::Output;
}

For slicing a Vec, the relevant implementation is:

impl<T, I> Index<I> for Vec<T>
where
    I: SliceIndex<[T]>,
{
    type Output = I::Output;
    // ...
}

and for slicing with I = Range<usize>, the associated type I::Output = [T]. Substituting the types, this means that we have a function of the form

fn index(vec: &Vec<T>, range: Range<usize>) -> &[T]

At first glance, this looks fine. The slice contains a subset of the elements in vec. But what about the length of the slice? The length of the slice may different from the length of the Vec; where is this length stored? The slice clearly knows its own length because it has a .len() method and performs bounds-checking while indexing. But, if the &[T] could only know about a subset of the bits in the vec as suggested earlier, it wouldn't know its own length.

It turns out that &[T] is not just a normal reference like &T; it's a "fat pointer". In other words, the type &[T] is handled specially be the compiler. It doesn't just store a pointer like &T, it also stores the length. You can verify this by looking at the size of &T versus &[T]:

println!("{}", ::std::mem::size_of::<&[i32]>());    // prints "16" on a 64-bit machine
println!("{}", ::std::mem::size_of::<&i32>());    // prints "8" on a 64-bit machine

The size of &[i32] is 16 because it stores the pointer (8 bytes) plus the length (another 8 bytes), while the size of &i32 is 8 because it only stores a pointer (8 bytes).

As far as I'm aware, the only other kind of "fat pointer" in current Rust is a trait object (&Trait), since trait objects need to a store a pointer to their vtable. Rust does not yet allow custom fat pointers (other than references to thin wrappers with an unsized member, which can only be produced with an unsafe pointer cast (see SliceInfo.as_ref() for an example)).

It should now be clear why we can't remove ArrayBase.slice() and ArrayBase.slice_mut() and replace them with Index and IndexMut implementations. Index and IndexMut require a reference to be returned, but the slice may have different shape/strides from the original array, and we need to store the shape and strides of the slice somewhere. Unlike &[T], we don't have special compiler support for storing the shape/strides of a slice of an array in a fat pointer, so we can't actually write an Index/IndexMut implementation that returns a slice of a portion of an array. The compiler would need to provide support for custom fat pointer types.

Now, let's take a look at conversions from views to owned arrays:

• &ArrayView<'a, A, D> → &Array<A, D> (this is a Deref conversion from ArrayView to Array): This is a conversion of the form &T -> &U. We can't do this because Array<A, D> needs to contain a Vec of the elements, and the view doesn't have one.
• &mut ArrayViewMut<'a, A, D> → &mut Array<A, D> (this is a DerefMut conversion from ArrayViewMut to Array): Same problem.
• ArrayView<'a, A, D> → &Array<A, D>: Same problem.
• ArrayViewMut<'a, A, D> → &mut Array<A, D>: Same problem.

It turns out that if we're very careful with the bitwise representation of ArrayBase (probably have to add #[repr(C)] and reorder the fields), I think we can go the other way (as long as the shape and strides of the original and view are the same) because the the data field of ArrayView/ArrayViewMut is zero-sized. So, in principle, I think we should be able to perform these conversions (implemented with a pointer cast and unsafe deref):

• &'a ArrayBase<S: Data, D> → &'a ArrayView<'a, A, D>
• &'a mut ArrayBase<S: Data, D> → &'a mut ArrayViewMut<'a, A, D>

At first glance, it looks like this means that we could implement Deref, DerefMut, Borrow, and BorrowMut for these conversions. In particular, a Borrow implementation would be really nice because it would allow us to use normal Cow with arrays. Unfortunately, it turns out that these conversions aren't sufficient to due the way Deref/DerefMut/Borrow/BorrowMut are defined.

We can't do this because 'a is an unconstrained lifetime parameter:

impl<'a, A, D> Deref for Array<A, D> {
    type Target = ArrayView<'a, A, D>;
    fn deref(&'a self) -> &'a ArrayView<'a, A, D> { ... }
}

Trying to implement Borrow like this

impl<'a, A, D> Borrow<ArrayView<'a, A, D>> for Array<A, D> {
    fn borrow(&'a self) -> &'a ArrayView<'a, A, D> { ... }
}

is incompatible with the trait due to the 'a being a generic parameter on the impl instead of a generic parameter on the borrow function.

The following would be compatible with the trait, and I think safe because even though the view has a 'static lifetime, it is hidden behind the &'a reference. However, it doesn't match the intended semantics of ArrayView due to the 'static lifetime:

impl<A, D> Borrow<ArrayView<'static, A, D>> for Array<A, D> {
    fn borrow<'a>(&'a self) -> &'a ArrayView<'static, A, D> { ... }
}

We could introduce another view-style variant of ArrayBase called ArrayBorrowed or something that doesn't carry a lifetime. This still isn't great for Borrow due to the conflicting implementation in the standard library impl<T> Borrow<T> for T where T: ?Sized. Alternatively, ArrayBorrowed could be another struct that's not ArrayBase, but then we'd need to add all the ArrayBase methods to it. Switching to a "common trait"-based implementation of n-D arrays (an ArrayBase trait) instead of a "common struct"-based implementation (the ArrayBase struct) would resolve this. IDK, this may be something to look into in the future.