The motivation for this post is to get some feedback on a potential solution to a problem discussed several times before. I have not seen this exact solution being discussed, but perhaps it is trivially bad without me realizing it. What I want answered is if it is worth pursuing the problem further or if by some detail of how the language or the compiler works it is inherently a bad idea.
The problem is concerned referencing a view in some larger array. I have attempted to structured the text to make it possible to skip the part of the problem formulation the reader is already familiar with.
Introduction
Today, the only viable way to create a view into an array is by defining a type that can act as a view reference. Let's use the struct below as a basis of discussion. An analog struct corresponding to a mutable reference must also be created, but the definition is omitted.
pub struct View<'a, T: 'a, const DIM: usize> {
data: std::ptr::NonNull<T>,
len: [usize; DIM],
stride: [usize; DIM],
phantom: std::marker::PhantomData<&'a T>,
}
This type will work fine to a large extent. Particularly it is possible to implement methods on the array type and View to index/slice/view parts of the array in several exotic ways. For an example of how this works in practice ndarray is great, although the corresponding view type in ndarray is a bit more complex it is conceptually the same.
Problem
The problem is not related to what is possible to do with these kinds of array views in Rust. It is purely related to ergonomics. But it is nonetheless severe enough that working with ndarray or any other dynamic array library in Rust feels out of place compared to other parts of the language. A lot of my initial expectations about how dynamic arrays in Rust should work is wrong. And I believe users familiar with the nice dynamic arrays from numpy or Matlab will be hesitant to use Rust for purposes where arrays are needed.
I have attempted to list up some of the ergonomics issue this
1. The Index trait
Since Rust's Index trait require returning a reference it is currently impossible to use indexing in Rust to create a view into an array. This require different methods to be created to compensate for the missing Index implementations. The solutions can be decent. but since "native" indexing is supported with much flexibility in specification in ranges for 1D arrays and slices, it is unfortunate that multi dimensional arrays cannot provide the same ergonomics.
Below is an example demonstrating indexing in ndarray compared to how it can be expected to work.
let array = ndarray::array![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
// This kind of indexing is unfortunately impossible
assert_eq!(
array[(0..2, 0..2)],
ndarray::array![[1, 2], [4, 5]]);
// This is how view indexing looks like
use ndarray::s;
assert_eq!(
array.slice(s![0..2, 0..2]),
ndarray::array![[1, 2], [4, 5]]);
2. AsRef, AsMut, Borrow, etc
The same issue with Indexing also exists with these AsRef kind of traits. For arrays to work as a reference when using the Rusts stdlib types as Cow it is important these traits are implemented. One workaround is to define the layout of the array type as an extended version of the View, like shown below.
#[repr(C)]
pub struct Array<T, const DIM: usize> {
data: std::ptr::NonNull<T>,
len: [usize; DIM],
stride: [usize; DIM],
// The rest of the fields are omitted
}
Now AsRef<View> can be implemented for Array by transmuting the reference. The big drawback is that the View layout need to be guaranteed stable, if not it is UB to use these methods. This means View and Array probably must be defined in the same crate, which is incompatible with problem #4.
3. AddAssign and friends
As discussed in [1] it is quite akward to use AddAssign and similar traits with Views such as defined above. Simply stated the intuitive way of adding a value to a column doesn't work.
// This does not compile
values.column_mut(0) += 1.;
The solution is quite unintuitively:
// This works but is not intuitive
*&mut values.column_mut(0) += 1.;
Even though we know that a View represents a reference to some Array there is no way to let the compiler know. If the compiler was aware that View was a reference it would be sufficient to write
// This works but is not intuitive
*values.column_mut(0) += 1.;
4. Implementing functions using views
In Rust, functions working on continuous arrays of memory can be general over a lot of different types. The important thing is that all these types can be referenced as slices. It would be possible to do the same for Views if everyone would agree on a single definition to use. Unfortunately this is not trivial as a requirement for implementing AsRef and friends (see #3) is that the layout of the slice definition never can change.
The motivation here is quite strong. Things like finite differences or image filters can be implemented once and for all in a function over a View instead for a specific Array implementation.
Previously suggested solutions
Generalize Index(Mut) to return proxy for references
This have been discussed in [2] [3]. The conclusion is that changing the Index(Mut) traits might be desirable when GAT support is landed. But even if it is desirable it is not trivial. The old traits can never be removed, due to backward compatibility. However, it is possible to get some future edition to point to new traits.
Even though this would fix #1 it doesn't automatically help with AsRef, AsMut, Borrow, etc or any of the other issues. This must therefore be considered a band-aid rather than a full solution.
Custom DST
Custom DSTs would be a great solution. This is previously discussed in [4] and [5]. Here, View would be the DST and a &View would be a (very) fat pointer incorporating stride and length information. This removes the need for a ViewMut as the mutability would be decided as in an ordinary reference.
This is a good solution to all of the issues. Unfortunately the full custom DST feature is not something that can be prioritized at the moment and the RFC is such postponed[5]. This is understandable as this array indexing problem is the main motivation of this feature.
The suggestion up for discussion
Instead of creating a full feature custom DST almost uniquely for solving this problem, we could create view as a native Rust type. We could either call it view<T, n> or something more in lines with the slice and array types like [n[T]]. Like for the custom DST solution View would be the DST and a &View would be a (very) fat pointer incorporating stride and length information.
I believe the main problem here is that a reference to a view would not simply be 2 x ptr_size but instead 1 + 2xn ptr_size. I have no idea how heavily rustc expects or optimizes on fat pointers being exactly twice the length of normal pointers, but this type would need to break this assumption.
Another drawback is that references are generally expected to be somewhat slim. A 4D view would be 9 x ptr_size. This might be acceptable due to there hardly being more efficient ways to represent these views and the overhead being quite expected when using Views.
