What was gained by not allowing Deref to move out anything?

1

Hello,

Several n-dimensional array projects for Rust are discussing (e.g. ndarray, mdarray) that it would be really nice to deref (parts of) arrays to custom wide pointers that would represent array slices (in analogy to the built-in Vec<T> and &[T]).

However custom DSTs are not a thing yet.

Trying to understand the current state of things, and the motivations behind, I wonder:

Wouldn't a Deref that allows moving out (that would be the DerefMove proposal, right?) be already sufficient to implement such custom smart pointers?

Actually, why is it that std::ops::Deref insists on returning a reference? The code example attached below works and demonstrates that a hypothetical MyDeref trait could take over the work that std::ops::Deref does today and in addition support use cases like the ones envisioned by the n-dimensional array libraries.

On this topic, the Rust book says:

The reason the deref method returns a reference to a value, and that the plain dereference outside the parentheses in *(y.deref()) is still necessary, is to do with the ownership system. If the deref method returned the value directly instead of a reference to the value, the value would be moved out of self. We don’t want to take ownership of the inner value inside MyBox<T> in this case or in most cases where we use the dereference operator.

So the reason why Deref does not allow moving out anything is to prevent a dereferencing operation moving out inner values of the container? I still don't quite get it. In the code snippet below MyDeref is implemented for &Vec<i32>, so it is not allowed to move out anything out of the container. If it was implemented for Vec<i32> it could just as well move out contents, but would also consume the container in doing so - so why not?

The restriction cannot be there for performance reasons, because moving out a struct of two pointer-sized entries is the same as returning a wide reference.

So, in summary, I'd be grateful for hints that help me understand why std::ops::Deref was not defined like the below MyDeref in the first place. I certainly must be overlooking something.

I'm aware of previous discussions of this and similar topics (e.g. Why does the Index trait require returning a reference?) but I do not feel that they fully address the questions that I pose here.

Many thanks!

use std::slice::Iter as SliceIter;

// Mockup of a real container (this could be an owned array).
pub struct MyVec(Vec<i32>);

// Mockup of a smart-pointer into that container (this could be
// a n-dimensional slice).
pub struct MySlice<'a> {
    data: *const i32,
    len: usize,
    _slice: std::marker::PhantomData<&'a [i32]>,
}

// Add some minimal functionality to MySlice.
impl<'a> IntoIterator for MySlice<'a> {
    type Item = &'a i32;
    type IntoIter = SliceIter<'a, i32>;

    fn into_iter(self) -> SliceIter<'a, i32> {
        let slice: &[i32];
        unsafe {
            slice = std::slice::from_raw_parts(self.data, self.len);
        }
        slice.iter()
    }
}

// What would be lost if std::ops::Deref was like this?
pub trait MyDeref {
    type TargetRef;

    // Required method
    fn myderef(self) -> Self::TargetRef;
}

// MyDeref works for the mockup container.
impl<'a> MyDeref for &'a MyVec {
    type TargetRef = MySlice<'a>;

    fn myderef(self) -> MySlice<'a> {
        MySlice {
            data: self.0.as_ptr(),
            len: self.0.len(),
            _slice: Default::default(),
        }
    }
}

// MyDeref also seems to be able to replace std::ops::Deref.
impl<'a> MyDeref for &'a Vec<i32> {
    type TargetRef = &'a [i32];

    fn myderef(self) -> &'a [i32] {
        self.as_slice()
    }
}

fn main() {
    let vec = vec![0, 1];
    let myvec = MyVec(vec![0, 1, 2]);

    let slice = vec.myderef();
    let myslice = myvec.myderef();

    // Types are as expected
    dbg!(std::any::type_name_of_val(&slice));   // &[i32]
    dbg!(std::any::type_name_of_val(&myslice)); // MySlice

    // MySlice works:
    for val in myslice {
        dbg!(val);
    }
}
1 Like
2

How would the compiler know whether to invoke the deref method on &YourType or &mut YourType (or Arc<YourType> etc etc)? Especially it they could return different types and the compiler had to call deref again on them. This creates an exponential number of candidates which are also ambiguous between each other.

This issue is avoided with Deref/DerefMut because they must return reference to the same target, so the resulting places will have the same type and only differ by the mutability, which can be determined as the last step. Ultimately this results in only a linear number of candidates.

5 Likes
3

Right. I note that a better way would be probably:

pub trait MyDeref2 {
    type TargetRef<'a> where Self: 'a;

    // Required method
    fn myderef2<'a>(&'a self) -> Self::TargetRef<'a>;
}

impl MyDeref2 for MyVec {
    type TargetRef<'a> = MySlice<'a>;

    fn myderef2<'a>(&'a self) -> MySlice<'a> {
        MySlice {
            data: self.0.as_ptr(),
            len: self.0.len(),
            _slice: Default::default(),
        }
    }
}

But this seems possible only since Rust 1.65, so perhaps the unavailability of generic associated types in early Rust is the reason for why Deref is defined the way it is?

The implementer of std::ops::Deref is allowed to return any type just as well (as long as it is a reference). Since it must be a reference, and since returning references to 'static data is not very useful in this context, in practice it must be a reference to something owned by Self, but is this really so different from the above MyDeref2?

In a sane library arrays would deref to slices, and slices again would only deref to slices. Not sure whether in practice an exponential explosion of combinations would be a problem.

4

Just found this, perhaps it's relevant:

5

That doesn't solve the issue I mentioned. What do you do for DerefMut? Will it also return a read-only MySlice?

No, the point is that DerefMut must return the same type as Deref (of course one behind a shared reference and the other behind a mutable reference, but the pointed type is the same).

MyMatrix would likely deref to MySlice and mutably deref to MySliceMut, just like Vec derefs to &[T] and &mut [T]. The difference however is that currently methods are only looked up on [T] (not on the references themselves), but with an owned parameter you need to lookup both MySlice and MySliceMut, which might deref to two different types and so on...

Edit:

That's part of the reason, but extensions to something like you described have been considered later (especially for index, but the same considerations apply for both) and these issues were found.

1 Like
6

The more you require in your trait definition, the stronger assumptions are possible by your downstream consumers.

Your proposed trait is so vague, it doesn't define anything of substance. Some type can be converted to some other type - great, now what? Not to mention that it's basically Into trait, just with an associated type rather than a type parameter.

The core purpose of Deref is to enable deref coercions: methods which are not found on the current type are searched for on its derefs. Deref coercions are already pretty scary, since they can complicate method resolution, resulting in very non-obvious method calls. Your proposal makes it worse, since now the method can be invoked on entirely arbitrary target types.

Besides, how would that even work? Currently if we try to call foo(&self) on x: T, there is a very simple sequence of method receivers to check: &x: &T, x.deref(): &<T as Deref>::Output, x.deref().deref(): &<T::Output as Deref>::Output, etc. Let's say deref could return an arbitrary type, e.g. some owned type S. So x.deref(): S. Now how could we call foo(&self) on it?

The receiver must be a reference. Do we implicitly insert & and try to call foo on &S? In that case what was the purpose of returning an owned type to begin with?

There is no way to turn foo(&self) into some foo_owned(self). So do we just immediately discard x.deref(), because a by-ref type cannot be called on an owned value? In that case, again, what was the point of allowing x.deref() to be an owned value? No method resolution will ever choose it.

Does it mean that x.deref() is used for method resolution with bar(self)? That looks like a recipe for confusion: we call what looks like a by-move method, but there is actually no move, because we have implicitly inserted a reference. Something entirely different and invisible is moved instead.

Rust puts a lot of effort into making variables passed by move, & and &mut distinguishable at a glance (as much as reasonably possible). This kind of method resolution would directly run counter to it, and could have other unintended consequences. For example, how would you chain x.deref().deref() if x.deref() was an owned value? I'd say this makes this kind of pass-mode-chainging resolution a nonstarter.

Overall, allowing to return arbitrary types just doesn't mix well with the goal "make method call more ergonomic without causing extra problems".

And you can already define MyDeref if you need it for any purpose other than method calls. So what's the point?

7

It would return MySliceMut, and there would by a conversion from MySliceMut to MySlice. But I see what you mean now. Thanks!

OK, so the fundamental reason why Deref has been defined the way it was, is that the language does not allow to implement a pair of custom reference types (e.g. MySlice and MySliceMut) that in all aspects behave as &[T] and &mut [T]. In other words: references are special. I guess that relaxing this restriction is what the various custom DST proposals are about.

8

(Obviously I'm not proposing anything - just trying to understand.)

This is std::ops::Deref:

pub trait Deref {
    type Target: ?Sized;
    fn deref(&self) -> &Self::Target;
}

This is MyDeref2 from above:

pub trait MyDeref2 {
    type TargetRef<'a> where Self: 'a;
    fn myderef2<'a>(&'a self) -> Self::TargetRef<'a>;
}

The method in the first trait takes a reference to self and returns a reference to some type with the same lifetime. The method in the second trait takes a reference to self and returns a reference-like struct with the same lifetime.

I do not see a big difference in terms of "strength of assumptions". Both traits are actually pretty weak in terms of assumptions I'd say. The usefulness of Deref comes from the associated mechanism of deref coercion. And so MyDeref2 would also requires such a mechanism, if it was ever to be adopted.

If I understand @SkiFire13 my "proposal" would actually work, if not for one crucial detail: handling of mutability. The proposal doesn't seem completely crazy, or it would not have been proposed independently before (see post 4 of this thread).

Indeed, for this proposal to be consistent an owned return type S would have to be treated as a custom "reference" type - which is what it is. So if foo was to take S by value, and x.deref(): S then the rules would have to be adapted such that foo(&x) would call foo(x.deref()).

Isn't this consistent (if we disregard the problems related to how to deal with mutability)?

Well, yes, it would have to. But since the type that bar takes by value is a custom reference type (that's what implementing MyDeref2 means), this is not really different from a function that takes a reference - that reference is passed by value after all.

I understand that there would be potential for abuse. People could impl MyDeref2 with huge target types so that an innocently looking call by reference would actually copy/move a lot of data. But doesn't the current Deref present the same kind of problem already? Implementers of Deref are free to perform arbitrary computation inside a deref method call. There are ways - for example there could be a lint against implementing MyDeref2 with huge target associated types.

The point would be exactly method and function calls. A numerical array library like ndarray could define a custom slice type that many methods/functions could accept instead of a reference to an array. This would mirror what the standard library does for vectors and strings. Follow the first link of my first post above for an in-depth discussion.

9

I see. So you're proposing Deref to return reference-like structs rather than arbitrary types. In that case, you first problem is that Rust has no concept of "reference-like" type. Just having a lifetime parameter doesn't make the type "reference-like". I can add a lifetime parameter to any type:

pub struct ReferenceLike<'a, T>(pub T, PhantomData<&'a T>);

References have many properties that other types cannot have: reborrowing, field projection, immutability and aliasing guarantees, dereference to a place expression, unsizing, and possibly others. None of those are possible for arbitrary types. Some may be possible in the future, but it's still a long way off.

Note that references are actual types in Rust's type system, not some magic "this should be handled via pointers" annotation like in C++. A method foo(&self) must actually take &T for some T. It can't just take something "reference-like", whatever that means. If you think otherwise, then you're not just proposing to change Deref, you're proposing a fundamental change to Rust's type system, which is an even harder sell. This means that your reference-like type must end up converted to a reference anyway, in which case what is its purpose in the first place?

Also, note that your original question "why wasn't Deref designed in a more general way" has an even simpler answer, regardless of any second-order consequences. The trait you propose simply wasn't possible when Deref was stabilized. The generic associated types didn't exist until a couple of years ago. Modifying Deref now is essentially impossible due to backwards compatibility.

3 Likes
10

For a different angle on the same thing, Deref and DerefMut are the traits that define something as "reference-like", and redefining them means that there's no way to make your type reference-like.

Now, Rust could have a trait like the one that's defined by the OP, and use that for coercion instead of Deref, but you'd still need Deref to allow you to say "this thing here, which is not a reference, is meant to be semantically the same as &Self::Target", and DerefMut to say "this thing is meant to be semantically the same as &mut Self::Target.

1 Like
11

Interesting idea. I've been a bit confused about how to best think about Deref:

  • On one hand, as you say, it the Deref trait defines the meaning of the dereference operator for a type, so it's fair to say that types that implement Deref are references.

  • On the other hand between Vec and slice (or between a nd-array and associated nd-slice), it's the Deref::Target that could be called reference.

You seem to be implying that two concepts are mixed in the Deref trait: that of being a reference and that of the coercion mechanism. Is this what you mean?

You mean this?

pub trait MyCoerce {
    type TargetRef<'a>: Deref
    where Self: 'a;

    fn mycoerce<'a>(&'a self) -> Self::TargetRef<'a>;
}

impl MyCoerce for MyVec {
    type TargetRef<'a> = MySlice<'a>;

    fn mycoerce<'a>(&'a self) -> MySlice<'a> {
        MySlice {
            data: self.0.as_ptr(),
            len: self.0.len(),
            _slice: Default::default(),
        }
    }
}

But how to impl<'a> Deref for MySlice<'a>?

12

I would say that Vec is semantically a reference to an owned, resizeable, mutable slice, and thus these are the same thing. Similarly, an nd-array is semantically an owned nd-slice, and it's thus reasonable to be able to treat an nd-array as a reference to an nd-slice.

If you don't have the semantics of a reference yourself, but you can cheaply give out a reference to something if I have a reference to you, then there's AsRef and AsMut. Similarly, there's the Borrow trait to indicate that you are not a T, but you can be treated as an &T where that's interesting.

pub struct MySlice<'a> {
    data: *const i32,
    len: usize,
    _slice: std::marker::PhantomData<&'a [i32]>,
}

impl<'a> Deref for MySlice<'a> {
    type Target = [i32];

    fn deref(&self) -> &[i32] {
        // SAFETY: MySlice ensures that `data` always points to at least `len` elements
        unsafe { std::slice::from_raw_parts(self.data, self.len) }
    }
}
2 Likes
13

Sure, this works because MySlice is a toy example and the corresponding reference (&[i32]) exists in the language. But imagine that MySlice represented something more general, for example a Python-like slice with a step, or an n-dimensional slice of a tensor.

14

Right, but until you've defined what MySlice looks like, and what the corresponding reference type is meant to be, it's impossible to define what impl Deref for MySlice is meant to look like. All I know about it is that it's got some shape that you're not telling me (but can use to shoot down solutions), and that you want it to in some way act like a reference.

impl Deref is there to let you say that "this thing, which looks like an owned thing, is actually an &SomeType in disguise"; but to implement it, you need to define what this thing is, and what SomeType is.

1 Like
15

Here is a more realistic but still very simple example. The following StepSlice is a type that I would call reference-like (it's like MySlice but with optional regular holes). But how to implement Deref for it? Is Deref really the definition ob being a reference in Rust?

Note that while this is a toy example, it captures the essence of an n-dimensional slice of an n-dimensional array: it is (1) not continuous in memory and (2) closed under the slicing operation (here: step_by).

use std::{iter, slice, ops};

// Placeholder for a smart-pointer into that container (this could be
// a n-dimensional slice).
pub struct StepSlice<'a> {
    slice: &'a [i32],
    step: usize,
}

impl<'a> IntoIterator for StepSlice<'a> {
    type Item = &'a i32;
    type IntoIter = iter::StepBy<slice::Iter<'a, i32>>;

    fn into_iter(self) -> iter::StepBy<slice::Iter<'a, i32>> {
        self.slice.iter().step_by(self.step)
    }
}

impl<'a> ops::Index<usize> for StepSlice<'a> {
    type Output = i32;

    fn index(&self, index: usize) -> &i32 {
        &self.slice[index * self.step]
    }
}

impl<'a> StepSlice<'a> {
    fn step_by(&self, step: usize) -> Self {
       StepSlice {
            slice: self.slice,
            step: self.step * step,
        }
     }
}
16

They asked above: what is the reference type meant to be?

17

That doesn't look reference-like to me, because it's not just referring to an owned object elsewhere; instead, it's adding behaviour as well, which means it's more than just a reference.

I wonder if your confusion is caused by [T] being an unsized type, and hence weird; because it's unsized, it's very difficult to actually have a real [T] that you own, but very common to have a reference to one (since Vec<T>, for example, is a [T] with extra book-keeping to allow it to be resized, while [T; N] is a [T] with exactly N elements at compile time, rather than being a size only known at runtime).

1 Like
18

StepSlice refers to an owned object just like a regular Rust slice does. In fact, a StepSlice instance contains a slice (but this is an implementation detail).

Rust lets one create an owned array of 10 elements. One may then create a slice that refers to the first 5 elements of that array. How is this conceptually different from creating a StepSlice that refers to every other element of the array?

My intention when starting this thread was to understand why the Defer trait does not support such extended references. After reading the various replies I believe that the reason is complications due to the interplay of Defer and DeferMut. But if for an instance we imagine that everything is immutable, then I believe that my above MyDeref2 trait could hypothetically replace Deref and allow implementation of more general reference-like types - like StepSlice.

19

It's not reference-like, it's array-like. So Index is the trait for that abstraction (and you've implemented it nicely!)

1 Like
20

It is different because of the definition of slice as a sequence of elements that are contiguous in memory. Slice is not an abstraction, it is a concrete type. That's why I say the abstraction you're looking for is Index.

Edit: Perhaps you might also want an abstraction for a container that has a length. I don't think there is one in Rust std, but you could define one if that would be useful to you. Not sure it's popular, but the cc-traits crate has a Len trait.

1 Like