Understanding Borrow and ToOwned

help
1

Hi everyone,

I'm working on mmtkvdb to provide a better way to store types such as (u32, Vec<u8>) without forcing the user of the crate to copy data. I currently use a trait Storable which can be implemented on dynamically-sized types (but is currently also implemented on the owned types).

I would like to clean that up and find a better mechanism that handles types str and String, [u8] and Vec<u8> etc. in an abstract way.

I've come across the following traits in the past quite often:

While I understand what these traits do, I don't understand why Borrow has the borrowed type as a type parameter (e.g. Borrow<B>)? Is there any case where an owned type will allow borrowing as several different types (under the rules of Borrow that require Eq and others to be consistent)? I understand this is required for AsRef, but I don't see why it's needed for Borrow. So why does Borrow not use an associated type as target type?

1 Like
2

It's perfectly fine to borrow an owned type as two different borrowed types. I don't see why this would necessarily violate consistency with Eq/Ord/Hash. Here's an implementation where they work together just fine.

3

Hmmm, I see. My question was less whether it's possible but more whether it's needed. But since it's possible it makes sense it's allowed to implement it multiple times (for different borrowed types). I currently just can't think of a good example where it's useful. Maybe using the newtype pattern could be such a use-case, where the newtype changes behavior or some semantics but not the behavior in regard to Eq/Hash/Ord.

Perhaps I should think of Borrow not like "going from the owned type to the borrowed type" but "going from the owned type to some borrowed type that is consistent in regard to Eq/Hash/Ord". What feels odd though is that the reverse mechanism, ToOwned, is tied to one specific owned type, i.e. I can't have multiple implementations for different string buffers, for example. Maybe that's needed to make to_owned not cause problems with type inference?

4

It's the other way around; see the AsRef docs. That is, Borrow is for whole-type "equivalent" borrows that things like HashMap can rely on. AsRef in contrast can be for individual fields (that may not hash the same, aren't equal, etc.)

Every T implements Borrow<T>.Thus every other implementation results in an implementation for more than one type parameter (including the other std impls).

2 Likes
5

Also, there is some history here that I'm not going to look up on mobile (sorry) - the PartialOrd and PartialEq traits are parameterized but Ord and Eq are not. They were for a period and there's an RFC that says they are, but the pre-1.0 stabilization (?) PR removed them while also claiming to be in line with the RFC (a failure of governance IMO but perhaps an irrelevant one by now; readding them would probably harm inference).

The parameters of all four, if I recall correctly, was in no small part motivated by the HashMap-like use cases. But by stabilization time, Borrowed/ToOwned filled that role.

(All from hopefully accurate memory.)

6

I don't think so; trait bounds will not be affected and calling ord() directly is rare.

The collections reform RFCs. I remember there were discussions about allowing ToOwned to have multiple owned types, but I'm not sure.

1 Like
7

Yeah, I just noticed that too! So it can't be an associated type.

8

Rfc 0439 is the one that parameterized comparison traits and got rid of Equiv.

Here is the parameter removing stabilization pr.

1 Like
9

In my case, it seems like I need a trait that allows me to go from the owned type to the (usual) borrowed type.

I finally ended up making my own type for that:

pub trait BorrowStorable
where
    Self: Sized + Borrow<Self::Stored> + Ord,
{
    type Stored: ?Sized + StorableWithOwned<Self>;
}

impl<T> BorrowStorable for T
where
    T: StorableWithOwned<T>,
{
    type Stored = Self;
}

impl<T> BorrowStorable for Vec<T>
where
    T: Ord,
    [T]: StorableWithOwned<Vec<T>>,
{
    type Stored = [T];
}

impl BorrowStorable for String {
    type Stored = str;
}

Which I can then use like this:

 unsafe impl<T1, T2> Storable for (T1, T2)
 where
-    T1: StorableWithOwned<T1> + StorableConstBytesLen,
-    T2: StorableWithOwned<T2>,
+    T1: BorrowStorable,
+    T2: BorrowStorable,
+    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
 {
-    const CONST_BYTES_LEN: bool = T2::CONST_BYTES_LEN;
+    const CONST_BYTES_LEN: bool = <T2 as BorrowStorable>::Stored::CONST_BYTES_LEN;
     type AlignedRef<'a> = Owned<Self>;
     type BytesRef<'a> = Vec<u8>
     where
         T1: 'a,
         T2: 'a;
     fn to_bytes(&self) -> Self::BytesRef<'_> {
-        let mut bytes = Vec::with_capacity(self.0.bytes_len() + self.1.bytes_len());
-        bytes.extend_from_slice(&self.0.to_bytes());
-        bytes.extend_from_slice(&self.1.to_bytes());
+        let mut bytes = Vec::with_capacity(self.0.borrow().bytes_len() + self.1.borrow().bytes_len());
+        bytes.extend_from_slice(&self.0.borrow().to_bytes());
+        bytes.extend_from_slice(&self.1.borrow().to_bytes());
         bytes
     }
     unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
-        let v1: T1 = T1::owned_from_bytes_unchecked(&bytes[0..T1::BYTES_LEN]);
-        let v2: T2 = T2::owned_from_bytes_unchecked(&bytes[T1::BYTES_LEN..]);
+        let v1: T1 = <T1 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[0..<T1 as BorrowStorable>::Stored::BYTES_LEN]);
+        let v2: T2 = <T2 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[<T1 as BorrowStorable>::Stored::BYTES_LEN..]);
         Owned((v1, v2))
     }
 }

Such that even if Vec<u8> is not Storable (you're supposed to use [u8]), I still have a (u64, Vec<u8>) being Storable.

But not sure if all that makes sense. I'm still working on it. I just shared it here to point out what was my original go: Have a trait that serves as a type constructor which goes from String to str (where I could use Deref maybe?) but also from i32 to i32 (where I can't use Deref), i.e. from an owned type to the immutable borrowed type.

StorableWithOwned, I defined like this:

pub trait StorableWithOwned<T>: Storable {
    /// Converts from byte slice into (owned) `Self`
    unsafe fn owned_from_bytes_unchecked(bytes: &[u8]) -> T;
}

impl<T, O> StorableWithOwned<O> for T
where
    T: ?Sized + Storable,
    for<'a> <<T as Storable>::AlignedRef<'a> as PointerIntoOwned>::Owned: IsType<O>,
{
    unsafe fn owned_from_bytes_unchecked(bytes: &[u8]) -> O {
        Self::from_bytes_unchecked(bytes).into_owned().identity()
    }
}

trait IsType<T> {
    /// Returns value with its type being same as the type argument
    fn identity(self) -> T;
}

impl<T> IsType<T> for T {
    fn identity(self) -> T {
        self
    }
}

Btw, I wonder if my IsType helper trait is something that's also commonly needed in other contexts. It's very generic actually, but I suppose we don't have something like that in std?

10

In general, I think this would require specialization. You can't just say, "For all T, T: Borrow<Target = T>, except that Vec<T>: Borrow<Target = [T]>, String: Borrow<Target = str>, PathBuf: Borrow<Target = Path>, etc." You'd have to explicitly specify every type that you want to have the first behavior.

11

You could also require that T: Deref, <T as Deref>::Target: ToOwned<Owned = Self>. That will be unambiguous.

12

Yeah I came across the same problem.

I had that idea too, but for types that are not Deref, this bound is not met, i.e. I can go from String to str, but not from i32 to i32.

But I'll have to do more research of my original/underlying problem to see what I actually need.

What I noticed is that Cow gets the borrowed type (and not the owned type) as type parameter. Beside having the easy way to go from the borrowed type to the owned type (via ToOwned), this also allows to have two distinct types Cow<'a, String> and Cow<'a, str>, of which only the first would have a .capacity, for example.

13

This is how I solved my problem.

14

To summarize the answers to the original post:

Question #1:

Answer #1:

Question #2:

Answer #2:

To give an example: String implements both Borrow<String> and Borrow<str>, so I can borrow it either as String or as str. And Borrow will assure that Ord behaves the same on the respective borrowed type (unlike AsRef).

This reminds me of the discussion in What is the difference between as_ref() & '&'. I would say that it's actually the main point of Borrow::borrow to be generic and to allow borrowing different types. Otherwise, we could just use &.

1 Like
15

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.