Love the idea!
Disclaimer: I am sketchy on the requirements and effects ofPhantomData, so I'll abstain from comments on that.
Differentiate Column and ColumnMut.
I'd advise calling this struct ColumnMut, and reserve Column for the non-mutable version.
Behold NonNull.
Rather than specifying as an invariant that ptr is non-null, you should use the NonNull type.
Apart from a better API and a better guarantee, this will also create a niche within the ColumnMut so that Option<ColumnMut> will have the same size as ColumnMut. Pretty neat.
pub struct ColumnMut<'a, T> {
ptr: NonNull<[T]>,
...
}
Consider zero-sized structs.
Slices of zero-sized structs are particular, as they reference a zero-sized array, and may have nigh arbitrary length.
You could either disable support for them outright -- panicking in the constructor for example -- or else you'll need to double check your implementation.
I'd advise creating a test with the largest Vec<()> you can get, getting a slice from that, and then testing operations on the two edge cases that are single row and single column (min/maxing length and period).
Consider implementing Default for ColumnMut.
You can use a dangling pointer and a length of 0.
(Performance) Consider a different representation.
The problem of the current representation is that len() uses / self.period. A division by a (large) integer is the slowest arithmetic operations possible: between 30 and 90 CPU cycles, when an addition/subtraction is 1 cycle and a multiplication 3 cycles. This is because it's implemented by trial division, primary school style.
It's all the more problematic here that you use len repeatedly, it's the basis of pretty much all other implementations. The cost is going to add up quickly.
Rather than storing the length of the slice (as part of [T]) you could instead directly store the length of the column (number of rows).
Similarly, you store the offset, requiring you to add it at every turn. Addition is fast (1 cycle) but that's an extra 8 bytes (+33%). Instead, you could just offset the pointer once and for all when creating the ColumnMut, and you'd be good to go.
pub struct ColumnMut<'a, T> {
ptr: NonNull<T>,
length: usize,
period: usize,
_lifetime: PhantomData<&'a mut [T]>,
}
impl ColumnMut<'a, T> {
/// Creates an instance of the given length, based on the given number
/// of rows and the column index.
///
/// # Safety
///
/// - The slice must be alive and must NOT be aliased for `'a`.
/// - All instances of `ColumnMut` referencing this slice MUST be defined
/// with the same number of rows and a distinct column index.
/// - `number_rows * number_columns` must be equal to `slice.len()`.
/// - `column_index` must be strictly less than `number_columns`.
pub unsafe fn new(
slice: NonNull<[T]>,
number_rows: usize,
number_columns: usize,
column_index: usize,
) -> ColumnMut<'a T> {
// Any safety invariant which CAN be verified SHOULD be verified in
// Debug mode.
debug_assert_eq!(number_rows * number_columns, slice.len());
debug_assert!(column_index < number_columns);
let length = number_rows;
let period = number_columns;
let _lifetime = PhantomData;
if length == 0 {
let ptr = slice.as_non_null_ptr();
return Self { ptr, length, period, _lifetime, };
}
// SAFETY:
// - `column_index` is within bounds of the original slice, since
// * `column_index < number_columns`,
// * `number_rows * number_columns == slice.len()`,
// * and `number_rows > 0`.
// - `column_index` does not overflow an `isize`, since it's within
// bounds of the slice and a slice size does not overflow an `isize`.
let ptr = unsafe { slice.as_non_null_ptr().add(column_index) };
Self { ptr, length, period, _lifetime, }
}
You may even consider using u32, instead of usize, as having more than 4 billions of columns, or 4 billions of rows, is fairly unlikely in the first place -- it requires 4 GB of memory for the smallest 1 byte struct.
(Safety) Use the unsafe_ops_in_unsafe_fn lint.
It requires using unsafe for unsafe operations even in unsafe functions, making them stand out, and ensuring you don't forget the matching SAFETY comment.
// In lib.rs or main.rs
#![deny(unsafe_ops_in_unsafe_fn)]
(Safety) Don't be greedy.
It's tempting to pack as much as possible in a single unsafe statement, but the problem is that it makes it hard to properly document why each individual operation is valid.
Instead, prefer splitting each operation in a separate block, unless the same justification can made for multiple operations at once.
(Safety) Don't repeat yourself.
It's not an advice specific to safety, but it's all the more important when safety's at stake.
Part of the reason for being "greedy" (packing statements, skimping on the SAFETY comment, ...) is that you're repeating yourself. And it'd be worse if you had the appropriate get and get_mut fallible implementation, as you'd have 4 implementations of getting an element.
Instead, do it ONCE and do it WELL.
(Safety) Avoid materializing the reference to the underlying slice.
I am surprised that MIRI isn't complaining -- maybe a gap in the tests?
When materializing &mut ... from raw pointers, I recommend never materializing intermediate references. There's too much of a chance of accidentally materializing an overlap: even if afterwards you only take one field or one element, if there's a moment in time where overlap exists, who knows what the compiler/optimizer might do.
Thus, I'd recommend sticking with pointer arithmetic until you have a pointer to a guaranteed not-to-overlap piece of memory, in your case, a T.
(Safety) Putting all those remarks together.
Focusing on the new stuff:
impl<'a, T> ColumnMut<'a, T> {
/// Returns a reference to the element at the specified `index`, if within bounds.
pub fn get(&self, index: usize) -> Option<&T> {
let pointer = self.get_pointer(index)?;
// SAFETY:
// - `pointer` is within bounds, as per `self.get_pointer`.
// - `pointer` is correctly aligned, and points to readable memory.
// - `self` has exclusive access to `*pointer`, guaranteeing the
// absence of mutable borrow from outside `self` for the lifetime
// of `&*pointer`.
// - `&*pointer` borrows `&self`, guaranteeing the absence of mutable
// borrow from `self` for its lifetime.
Some(unsafe { &*pointer })
}
/// Returns a reference to the element at the specified `index`, if within bounds.
pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
let pointer = self.get_pointer(index)?;
// SAFETY:
// - `pointer` is within bounds, as per `self.get_pointer`.
// - `pointer` is correctly aligned, and points to readable memory.
// - `self` has exclusive access to `&mut *pointer`, guaranteeing the
// absence of borrow from outside `self` for the lifetime of
// `&mut *pointer`.
// - `&mut *pointer` borrows `&self` mutably, guaranteeing the absence
// of borrow from `self` for its lifetime.
Some(unsafe { &mut *pointer })
}
// Returns a pointer to the element at the specified `index`, if within bounds.
fn get_pointer(&self, index: usize) -> Option<NonNull<T>> {
if index >= self.length {
return None;
}
if mem::size_of::<T>() == 0 {
return Some(self.ptr);
}
// SAFETY:
// - `index * self.period` is within bounds of the original slice.
// - `index * self.period` does not overflow an `isize`, since it's
// within bounds of the original slice and a slice size does not
// overflow an `isize`.
let pointer = unsafe { self.ptr.as_ptr().add(index * self.period) };
NonNull::new(pointer)
}
Having written the fallible versions, the infallible ones are dead easy:
impl<'a, T> Index<usize> for ColumnMut<'a, T> {
type Output = T;
fn index(&self, index: usize) -> &Self::Output {
let Some(element) = self.get(index) else {
panic!("{index} is out of bounds (>= {})", self.length);
};
element
}
}
impl<'a, T> IndexMut<usize> for ColumnMut<'a, T> {
fn index_mut(&self, index: usize) -> &mut Self::Output {
let Some(element) = self.get_mut(index) else {
panic!("{index} is out of bounds (>= {})", self.length);
};
element
}
}
Use a better named argument for ColumnIterMut::new
That period is fairly confusing. This is the number of columns, just name it so.
(Safety) What about ColumnIterMut?
I am uneasy, once again, due to the presence of the mutable slice.
After obtaining a ColumnMut from the iterator, you have both:
- A mutable slice within
ColumnIterMut.
- A
ColumnMut instance allowing to materialize a mutable reference to elements of this mutable slice.
This is a recipe for disaster, in my view, and I'd feel better if ColumnIterMut instead embedded a NonNull<[T]> so that if anyone wants elements out of that, they'll have to first do a safety assessment.
Put together:
pub struct ColumnMutIter<'a, T> {
slice: NonNull<[T]>,
length: usize,
period: usize,
offset: usize,
_lifetime: PhantomData<&'a mut [T]>,
}
impl<'a, T> ColumnMutIter<'a, T> {
pub fn new(slice: &'a mut [T], number_columns: usize) -> Self {
assert!(number_columns > 0);
// Consider this case, silent failure seems odd.
debug_assert!(number_columns <= slice.len());
let slice = NonNull::from(slice);
let length = slice.len() / number_columns;
let period = number_columns;
let offset = 0;
let _lifetime = PhantomData;
Self { slice, period, offset, _lifetime }
}
}
impl<'a, T> Iterator for ColumnMutIter<'a, T> {
type Item = ColumnMut<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
if self.offset < self.period {
let result = ColumnMut::new(self.slice, self.length, self.period, self.offset);
self.offset += 1;
Some(result)
} else {
None
}
}
}
The length in my implementation is "overkill". You could do without if you removed the matching debug statement in ColumnMut::new. But it doesn't cost much to keep it, so why not?
(Safety) Your Send and Sync look odd.
A ColumnMut is a reference to a slice, not a slice itself, so I'd change the where clauses to &'a mut [T]: Send (or Sync) to match. Probably inconsequential, but it'd match exactly, rather than closely, and who knows what differences lurk there?
Where are the tests?
You didn't show any test.
It's important to have good test coverage for unsafe code, because the only analysis tools that you have (MIRI, Sanitizers, Valgrind, ...) only check that the code that is running looks OK.
So, first things first, write tests as you would normally. You want to verify that each function, in isolation, works as expected, including in edge cases:
- This means checking zero-sized elements.
- This means using
cargo tarpaulin (or equivalent) to check code coverage and verifying that you exercise all code-paths.
It's unsafe code, be thorough.
On top, you also need some specific testing techniques for unsafe code.
You want to check that borrow-checking works, or that Send and Sync are not implemented when they should not be. It seems silly, but when you write unsafe code and materialize references manually, you could have a fn get(&self) -> &'static T and it would compile... and because the lifetimes differ, it would not borrow self. Or you could accidentally delete that where clause on impl Send. Time to be paranoid.
You should (ab)use documentations tests, as they can test that compilation fails for a snippet:
#[cfg(test)]
#[doc(hidden)]
pub mod compiletests {
/// ```compile_fail:Exxx
/// let mut array = [1, 2, 3];
/// let column = ColumnMut::from_slice(&mut array, 3, 0);
///
/// let first = column.get(0);
/// std::mem::drop(column); // first should borrow until next line.
/// std::mem::drop(first);
/// ```
pub fn column_mut_get_borrow() {}
}
And finally, you want to write tests specifically exercising overlapping borrows:
- Between
ColumnMutIter and ColumnMut: create a column, use it to access an element, create another column, use the element from the first.
- Between
ColumnMut instances: create two columns, grab an element (mutably) from each, use swap between them.
It's those tests that'll really validate whether the Stacked Borrow model is okay with what you're doing, or not.
