I was playing with some code, trying to see how wild I can get.
The basic idea came to me when implementing merge sort with a custom comparator. We need to pass down the comparator (impl FnMut), but we cannot pass it owned because we need to pass it twice (for each subroutine). The classic workaround is to take &mut impl FnMut. But then, if the comparator is a Zero-Sized-Type (which is the case in the common case of just forwarding to the sorted type's PartialOrd implementation, via PartialOrd::lt which is a function item those a ZST), we pass down a real reference while we could avoid it, which is bad for optimization. Maybe the compiler can eliminate this parameter, but can we do better?
So, using specialization I thought to build a type that constructs the instance on-the-fly for ZSTs but stores a real reference for other types. This also requires generic_const_exprs, so let's go wild with the most unstable features!
First, we need a trait to represent ZSTs so we can specialize on it:
#![feature(specialization, generic_const_exprs)]
trait IsZst {}
struct Assert<const COND: bool>;
trait IsTrue {}
impl IsTrue for Assert<true> {}
impl<T> IsZst for T where Assert<{ std::mem::size_of::<T>() == 0 }>: IsTrue {}
Then we can build another trait, that will have two associated types: one which is the shared reference type, and the other which is the mutable reference type:
pub trait EfficientZstRep {
type SharedRef<'a>: Deref<Target = Self> + From<&'a Self> + Copy
where
Self: 'a;
type MutRef<'a>: Deref<Target = Self> + DerefMut + From<&'a mut Self>
where
Self: 'a;
}
The default implementation is easy - just use normal references:
impl<T: ?Sized> EfficientZstRep for T {
default type SharedRef<'a> = &'a T
where
Self: 'a;
default type MutRef<'a> = &'a mut T
where
Self: 'a;
}
For ZSTs, we need to have our own structs:
pub struct SharedZstRef<'a, T>(PhantomData<&'a T>);
impl<'a, T: IsZst> From<&'a T> for SharedZstRef<'a, T> {
#[inline(always)]
fn from(_v: &'a T) -> Self {
Self(PhantomData)
}
}
impl<T: IsZst> Deref for SharedZstRef<'_, T> {
type Target = T;
#[inline(always)]
fn deref(&self) -> &Self::Target {
unsafe { NonNull::dangling().as_ref() }
}
}
impl<T> Clone for SharedZstRef<'_, T> {
fn clone(&self) -> Self {
*self
}
}
impl<T> Copy for SharedZstRef<'_, T> {}
pub struct MutZstRef<'a, T>(PhantomData<&'a mut T>);
impl<'a, T: IsZst> From<&'a mut T> for MutZstRef<'a, T> {
#[inline(always)]
fn from(_v: &'a mut T) -> Self {
Self(PhantomData)
}
}
impl<T: IsZst> Deref for MutZstRef<'_, T> {
type Target = T;
#[inline(always)]
fn deref(&self) -> &Self::Target {
unsafe { NonNull::dangling().as_ref() }
}
}
impl<T: IsZst> DerefMut for MutZstRef<'_, T> {
#[inline(always)]
fn deref_mut(&mut self) -> &mut Self::Target {
unsafe { NonNull::dangling().as_mut() }
}
}
impl<T: IsZst> EfficientZstRep for T {
type SharedRef<'a> = SharedZstRef<'a, T>
where
Self: 'a;
type MutRef<'a> = MutZstRef<'a, T>
where
Self: 'a;
}
And now shared references work great! (Well, a little verbose, but who cares?)
fn foo<T: Fn()>(v: T) {
bar::<T>(<_>::from(&v));
}
fn bar<T: Fn()>(v: <T as EfficientZstRep>::SharedRef<'_>) {
v();
bar::<T>(v);
bar::<T>(v);
}
But with mutable references we got a problem: shared references are Copy, so we can use them twice, but mutable references are not. Usually, they are automagically reborrowed, so it looks like they are copied, but this is a different mechansim.
The usual workaround when you have a type that wrap mutable references (see e.g. the unstable std::io::BorrowedCursor, or Pin's as_mut()) is to have some method that take &'b mut self and returns Self with 'b lifetime. Let's express that in a trait:
pub trait EfficientZstRep {
type SharedRef<'a>: Deref<Target = Self> + From<&'a Self> + Copy
where
Self: 'a;
type MutRef<'a>: Deref<Target = Self> + DerefMut + Reborrow + From<&'a mut Self>
// `Reborrow` is new!
where
Self: 'a;
}
pub trait Reborrow: Deref {
type Result<'a>: Deref<Target = Self::Target> + DerefMut + Reborrow + From<&'a mut Self::Target>
where
Self: 'a;
fn reborrow(&mut self) -> Self::Result<'_>;
}
impl<T: ?Sized> Reborrow for &'_ mut T {
type Result<'b> = &'b mut T
where
Self: 'b;
#[inline(always)]
fn reborrow(&mut self) -> Self::Result<'_> {
&mut **self
}
}
impl<T: IsZst> Reborrow for MutZstRef<'_, T> {
type Result<'b> = MutZstRef<'b, T>
where
Self: 'b;
#[inline(always)]
fn reborrow(&mut self) -> Self::Result<'_> {
Self(PhantomData)
}
}
But unfortunately this doesn't work:
fn foo<T: FnMut()>(mut v: T) {
bar::<T>(<_>::from(&mut v));
}
fn bar<T: FnMut()>(mut v: <T as EfficientZstRep>::MutRef<'_>) {
v();
bar::<T>(v.reborrow());
bar::<T>(v);
}
error[E0308]: mismatched types
--> src/main.rs:124:14
|
124 | bar::<T>(v.reborrow());
| -------- ^^^^^^^^^^^^ expected `EfficientZstRep::MutRef`, found `Reborrow::Result`
| |
| arguments to this function are incorrect
|
= note: expected associated type `<T as EfficientZstRep>::MutRef<'_>`
found associated type `<<T as EfficientZstRep>::MutRef<'_> as Reborrow>::Result<'_>`
= note: an associated type was expected, but a different one was found
note: function defined here
--> src/main.rs:122:4
|
122 | fn bar<T: FnMut()>(mut v: <T as EfficientZstRep>::MutRef<'_>) {
| ^^^ -----------------------------------------
help: try removing the method call
|
124 - bar::<T>(v.reborrow());
124 + bar::<T>(v);
|
The problem is that the compiler is unable to conclude that v.reborrow() is also MutRef, just with another lifetime.
Trying to get rid of the explicit ::<T> doesn't work either:
fn bar<T: FnMut()>(mut v: <T as EfficientZstRep>::MutRef<'_>) {
v();
bar(v.reborrow());
bar::<T>(v);
}
error[E0282]: type annotations needed
--> src/main.rs:124:5
|
124 | bar(v.reborrow());
| ^^^ cannot infer type of the type parameter `T` declared on the function `bar`
|
help: consider specifying the generic argument
|
124 | bar::<T>(v.reborrow());
| +++++
error[E0283]: type annotations needed
--> src/main.rs:124:5
|
124 | bar(v.reborrow());
| ^^^ cannot infer type of the type parameter `T` declared on the function `bar`
|
note: multiple `impl`s or `where` clauses satisfying `_: FnMut<()>` found
--> src/main.rs:122:11
|
122 | fn bar<T: FnMut()>(mut v: <T as EfficientZstRep>::MutRef<'_>) {
| ^^^^^^^
= note: and more `impl`s found in the following crates: `alloc`, `core`:
- impl<A, F> FnMut<A> for &F
where A: Tuple, F: Fn<A>, F: ?Sized;
- impl<A, F> FnMut<A> for &mut F
where A: Tuple, F: FnMut<A>, F: ?Sized;
- impl<Args, F, A> FnMut<Args> for Box<F, A>
where Args: Tuple, F: FnMut<Args>, A: Allocator, F: ?Sized;
note: required by a bound in `bar`
--> src/main.rs:122:11
|
122 | fn bar<T: FnMut()>(mut v: <T as EfficientZstRep>::MutRef<'_>) {
| ^^^^^^^ required by this bound in `bar`
help: consider specifying the generic argument
|
124 | bar::<T>(v.reborrow());
| +++++
And I think that even if this would pass inference, this still wouldn't work as this will create infinite generic instantiations.
I also tried to create a giant where clause that will convince the compiler the types are the same:
pub trait Reborrow: Deref {
type Result<'a>: Deref<Target = Self::Target> + DerefMut + Reborrow + From<&'a mut Self::Target>
where
Self: 'a,
Self::Target: EfficientZstRep<MutRef<'a> = Self::Result<'a>>;
fn reborrow(&mut self) -> Self::Result<'_>;
}
But this doesn't work either:
error[E0275]: overflow evaluating the requirement `<&mut T as Reborrow>::Result<'_> == <T as EfficientZstRep>::MutRef<'_>`
--> src/main.rs:37:31
|
37 | fn reborrow(&mut self) -> Self::Result<'_> {
| ^^^^^^^^^^^^^^^^
error[E0275]: overflow evaluating the requirement `<MutZstRef<'_, T> as Reborrow>::Result<'_> == MutZstRef<'_, T>`
--> src/main.rs:96:31
|
96 | fn reborrow(&mut self) -> Self::Result<'_> {
| ^^^^^^^^^^^^^^^^
I understand why - as opposed to bounds after the colon in GATs, bounds in the where clause are something the implementor must consider and not the user - but I haven't found a way to specify this bound within the colon.