Smart pointer which owns its target

See also bit string on Wikipedia. :stuck_out_tongue_winking_eye:

But today, "string" is more a synonym for some non-indexable UTF-8 Unicode beast, which isn't really acting like an array of characters anymore :sweat_smile:.

2 Likes

After looking at the trait implementations for std::boxed::Box, std::borrow::Cow as well as @conradludgate's into_owned::IntoOwned trait, I made a new version of deref_owned (0.2.0).

I added a test case that looks like this:

#[test]
fn test_generic_fn() {
    fn generic_fn(arg: impl IntoOwned<Owned = String> + Borrow<str>) {
        let borrowed: &str = arg.borrow();
        assert_eq!(borrowed, "Echo");
        let owned: String = arg.into_owned();
        assert_eq!(owned, "Echo".to_string());
    }
    generic_fn(Owned("Echo".to_string()));
    generic_fn(Cow::Owned("Echo".to_string()));
    generic_fn(Cow::Borrowed("Echo"));
    generic_fn("Echo");
}

This resembles a bit the example from @conradludgate (not a contribution):

fn check<S: IntoOwned<str>>(s: S) -> String {
    s.into_owned()
}

let _foo = check("foo"); // will clone
let _bar = check(Owned("bar".to_owned())); // will not clone twice (unlike regular ToOwned)

@conradludgate: Do you think the new version 0.2.0 with implementations for Borrow would cover your use case now as well?

Counterexample: ManuallyDrop.

Owned is ManuallyDrop but with a drop implementation :slight_smile:

I think it's reasonable to say that the term “smart pointer” requires being a “pointer”. But I also think this is a useless term for the purpose of API design, and we should prefer much less ambiguous terms like “stable deref address.”

See also

“smart pointer” is a much more well-defined concept in C++... at least if you allow std::optional to be a smart pointer. In C++ the most useful concept for “smart pointer” would likely be implementing operator * and operator -> to T.

For Rust, that's impl Deref plus maybe impl Borrow for “acts like T.”

See also https://en.cppreference.com/w/cpp/memory

Smart pointers enable automatic, exception-safe, object lifetime management.

I think I was attempting to discuss two things at the same time (which are related though):

  • A trivial Deref wrapper (avoiding the term "smart pointer" now :innocent:)
  • A trait IntoOwned, which allows (consuming) conversion into an "owned" type (whatever "owned" means; this can be discussed)

I think there is a use case for a trivial Deref wrapper in connection with GATs (Playground example given in my post #16 above). This allows abstraction over &'_ T and SeeminglyUselessWrapper<T> (aka Owned<T>) when using a GAT with a Deref<Target = T> bound.

Now the IntoOwned (or PointerIntoOwned) trait is a different issue. I wanted to not having to specify the owned type when performing the conversion, hence I used an associated type (similar to std::borrow::ToOwned::Owned):

/// Pointer types that can be converted into an owned type
pub trait IntoOwned: Sized + Deref {
    /// The type the pointer can be converted into
    type Owned: Borrow<<Self as Deref>::Target>;
    /// Convert into owned type
    fn into_owned(self) -> Self::Owned;
}

(Version with Deref as supertrait)

Of course, I could use a type argument T instead, and convert into <T as ToOwned>::Owned> (instead of IntoOwned::Owned). But this requires having a type T: ToOwned. I think in most cases this is no problem because there is an impl<T> ToOwned for T where T: Clone and most types are Clone:thinking: but what if I deal with types that cannot be cloned at all for some reason? (Not sure if that's a real problem and if I'm overlooking the whole issue correctly.)

I currently feel like the question what is the "owned" type is a semantic one. This is another reason why I believe an associated type is the right choice. The implementation can set the corresponding "owned" type. Here is what I came up with so far:

  • &'a T<T as ToOwned>::Owned
  • Cow<'a, T><T as ToOwned>::Owned
  • Owned<T>T
  • Box<T>Box<T>
  • Vec<T>Vec<T>
  • StringString

Note the last three fall a bit out of line.

Saying that converting Vec<T> into its owned type is a no-op helps me to get rid of this construct: mmtkvdb::owning_pointer::OwnedPointer (the name is a bit awkward, it's basically the same as Owned<T> but doesn't dereference to T but to the value pointed-to by T).

Doing this for String, Vec<u8>, Box<[u8]>, and so on as well, might make some other things easier too:

fn generic_fn(arg: impl IntoOwned<Owned = String> + Borrow<str>) {
    let borrowed: &str = arg.borrow();
    assert_eq!(borrowed, "Echo");
    let owned: String = arg.into_owned();
    assert_eq!(owned, "Echo".to_string());
}
generic_fn("Echo".to_string());
generic_fn(Owned("Echo".to_string()));
generic_fn(Cow::Owned("Echo".to_string()));
generic_fn(Cow::Borrowed("Echo"));
generic_fn("Echo");

Note that if the owned type of Box<T> is Box<T>, then IntoOwned::into_owned() is not the same as Nightly's Box::into_inner().

Overall I'm quite confused about this issue, and I feel particularly insecure about IntoOwned and its semantics.

I published a new version 0.3.0 of deref_owned yesterday.

As said in my previous post, my main insight was that Box::into_inner is semantically different from IntoOwned::into_owned. All of

are already "owning" smart pointers. Note that there currently is no trait in std which classifies them as "smart pointers owning their pointee" or "smart pointers which could be converted into a smart pointers owning their pointee" (by a no-op/identity operation). They all implement Deref, but Deref is also implemented by &'a T.

Now &'a T isn't a smart pointer owning its pointee, but it's a reference which could be converted into a smart pointer owning the pointee if T implements ToOwned (and because a reference is Copy).

Defining IntoOwned

So let's see how we can find an abstraction for a pointer-like type that can be converted into an owned type while being consumed (which we will name IntoOwned).

First of all, we must demand that Deref is a supertrait, because Deref is what makes a type a pointer-like type. Moreover, such type must be Sized, because we want to pass it by-value to the conversion function. Hence we get:

pub trait IntoOwned: Sized + Deref

(as in line 91 in lib.rs of deref_owned)

Secondly, we need to know the type of the conversion result. Akin to ToOwned::Owned, this should be an associated type, such that we don't need to know the owning type (edit: what I mean is that we don't need to pick an owning type later when doing a conversion into an owned type; of course we still need to know it when implementing IntoOwned for a particular type). We want to be able to simply write .into_owned() without having to specify a type (same as when we use .to_owned()).

Here is how the associated type looks like:

pub trait IntoOwned: Sized + Deref {
    type Owned: Borrow<<Self as Deref>::Target>;
    /* … */

(as in line 93 in lib.rs of deref_owned)

By adding the bound IntoOwned::Owned: Borrow<<Self as Deref>::Target>, we demand that it's possible to get a borrow from the resulting type to our pointee (which is <Self as Deref>::Target), thus that Eq and Ord can be used consistently during all these operations. I.e. we say we must be able to get back again from the owned type to the borrowed type (this is just like the bound ToOwned::Owned: Borrow<Self>).

Finally, we need the actual conversion method:

    fn into_owned(self) -> Self::Owned;

(as in line 95 in lib.rs of deref_owned)

This consumes self and returns an owned type. The owned type (Self::Owned) isn't necessarily a pointer-like type (there is no Deref bound on IntoOwned::Owned), but we can go back from the owned type to the borrowed type using Borrow due to the previously added bound IntoOwned::Owned: Borrow<<Self as Deref>::Target>.

Implementing IntoOwned

Now let's see how IntoOwned is implemented in each case:

IntoOwned for &'a T

impl<'a, T> IntoOwned for &'a T
where
    T: ?Sized + ToOwned,
{
    type Owned = <T as ToOwned>::Owned;
    fn into_owned(self) -> Self::Owned {
        self.to_owned()
    }
}

(as in lines 98 to 106 in lib.rs of deref_owned)

We can only convert a reference to an owned type if the referenced type T implements ToOwned. hence we need a bound T: ToOwned. The conversion then happens using ToOwned::to_owned.

IntoOwned for Cow<'a, T>

impl<'a, T> IntoOwned for Cow<'a, T>
where
    T: ?Sized + ToOwned,
{
    type Owned = <T as ToOwned>::Owned;
    fn into_owned(self) -> <Self as IntoOwned>::Owned {
        Cow::into_owned(self)
    }
}

(as in lines 108 to 116 in lib.rs of deref_owned)

Here, we simply forward to the already existing method Cow::into_owned. Same as in the case of an ordinary reference, our result is <T as ToOwned>::Owned.

IntoOwned for Box<T>, Vec<T>, and String

These implementations are a no-op. That is because Box<T>, Vec<T>, and String are smart pointers which are already owned and where you can borrow their pointee, i.e. they already fulfill the bound Self: Borrow<<Self as Deref>::Target>.

Hence we simply do (example given for Vec<T> but it also applies to the other):

impl<T> IntoOwned for Vec<T> {
    type Owned = Self;
    fn into_owned(self) -> Self::Owned {
        self
    }
}

(as in lines 125 to 144 in lib.rs of deref_owned)

IntoOwned for T (such as i32) :interrobang:

But what if we have an owned value such as an integer? It is already owned. So there shouldn't be any problem, right?

i32 does not implement Deref<Target = i32>. It must not implement Deref because it is not a pointer-like type. But because it doesn't implement Deref, it cannot implement IntoOwned either :weary:.

This normally isn't a real problem because we just use i32 and we're happy. But when we do generic programming, we might not return a certain type T but a pointer-like type which points to T. Look at mmtkvdb::storable::Storable for an updated real-world example, which uses IntoOwned in a bound on a generic associated type (GAT):

pub unsafe trait Storable: Ord {
    /// Pointer to aligned version of `Self`
    ///
    /// This can be a simple reference ([`&'a Self`](prim@reference)) if there
    /// are no requirements for memory alignment, or can be a smart-pointer
    /// (like [`Owned<Self>`](Owned) or [`Vec`]) which drops the re-aligned
    /// copy when the smart-pointer is dropped.
    type AlignedRef<'a>: Deref<Target = Self> + IntoOwned;
    /* … */
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_>;
    /* … */
}

This trait is used, for example, by mmtkvdb::Txn::get:

fn get<'kr, K, V, C, KRef>(
    &self,
    db: &Db<K, V, C>,
    key: KRef
) -> Result<Option<V::AlignedRef<'_>>, Error> where
    K: ?Sized + Storable + 'kr,
    V: ?Sized + Storable,
    C: Constraint,
    KRef: StorableRef<'kr, K>, 

This looks horribly complex, but lets focus just on the (successful) return type Option<V::AlignedRef<'_>>. We basically return a pointer-like type to the stored value.

If we retrieve a string, then .get simply returns an ordinary reference to memory-mapped data on disk. But for some types like integers, we cannot do it becasue the memory-mapped data on disk will not have proper memory alignment (LMDB doesn't guarantee proper alignment). Here we must create a re-aligned copy of the data on disk. Freeing that memory should happen once the reference is no longer needed. This calls for a SMART POINTER!

And this smart pointer is exactly what Owned is. It is a wrapper which serves as a smart pointer to the wrapped value:

/// Smart pointer to owned inner value
#[derive(Clone, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Owned<T>(pub T);

impl<T> Deref for Owned<T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

/* … */

(as in lines 22 to 31 in lib.rs of deref_owned)

In case of mmtkvdb, this is used to implement Storable for integers, such as i32:

macro_rules! impl_storable_fixed_size_force_align {
    ($type:ty, $optimize_int:expr) => {
        unsafe impl Storable for $type {
            /* … */
            type AlignedRef<'a> = Owned<Self>;
            /* … */
            unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
                Owned(read_unaligned(bytes.as_ptr() as *const Self))
            }
        }
        /* … */
    };
}

(link to source)

Now let's get back to our IntoOwned trait. How do we implement it for Owned? It's trivial!

impl<T> IntoOwned for Owned<T> {
    type Owned = T;
    fn into_owned(self) -> Self::Owned {
        self.0
    }
}

(as in lines 118 to 123 in lib.rs of deref_owned)

To convert an Owned<T> into its pointee, we can simply extract the wrapped value of type T. Note that T fulfills the Borrow bound on IntoOwned::Owned because there is an implementation of Borrow<T> for any T.

Now how can we use this? Let's look at mmtkvdb again:

pub trait Txn {
    /* … */
    /// Get owned value from database
    fn get_owned<'a, 'kr, K, V, C, KRef>(
        &'a self,
        db: &Db<K, V, C>,
        key: KRef,
    ) -> Result<Option<<<V as Storable>::AlignedRef<'a> as IntoOwned>::Owned>, io::Error>
    where
        K: ?Sized + Storable + 'kr,
        V: ?Sized + Storable,
        C: Constraint,
        KRef: StorableRef<'kr, K>,
    {
        Ok(self.get(db, key)?.map(|x| x.into_owned()))
    }
    /* … */
}

(link to source)

Here .into_owned is used to convert the pointer-like type into the pointee. In case of an Owned<i32>, for example, this happens without unnecessary cloning (the cloning for memory re-alignment did already happen, we don't need to clone again).


I hope this made my motivations a bit more clear.

1 Like

It's for this reason that I posit that IntoOwned wants Borrow and not Deref as a supertrait. Borrow is the existing trait that allows taking both references and T by value, so if IntoOwned wants to allow by-value, it seems incorrect to require a pointer-like type.

So what exactly breaks if you instead define IntoOwned as

pub trait IntoOwned<T>: Sized + Borrow<T> {
    type Owned: Borrow<T>;
    /* … */

?

I suspect it's this:

because if T is an owning type, then &U has two options: it could be a borrow of owning U, or it could be owning &U. Cow<U> could convert to U::Owned or Cow<U>. An explicit 'static bound on Owned isn't really helpful either, as the issue still exists for static references.

What I think is missing is in fact a definition of “owned.” I think it's “does not have a lifetime parameter,” but there's no way to provide a blanket implementation for owned types under this definition without also including unowned types.

What the Owned wrapper is thus doing is saying that yes, T is an owned type for the purpose of IntoOwned. (But unintuitively, Owned isn't, unless of course it is itself contained in another Owned.)

For this reason, Owned feels significantly more like a workaround than an actual productive type. But the thing is, even with Owned, &&T's “owned” type is &T, which doesn't meet our definition of “owned,” and at that, implements IntoOwned::Owned = T.

Perhaps it should be an invariant that typeof(x.into_owned()) == typeof(x.into_owned().into_owned()). Using Self::Owned = Owned<T> does seem reasonable for &T.... Alternatively, perhaps this wants for fully general specialization that allows specializing on associated types. That would give us a default implementation on T of returning itself and on &T of returning (*self).clone().into _owned(), as well as further specialized for Cow.

The compiler absolutely can't do this yet, but it'd look something like

pub trait IntoOwned: Sized {
    type Owned: Owned;
    fn into_owned(self) -> Self::Owned;
}

pub trait Owned = IntoOwned<Owned=Self>;

impl<T> IntoOwned for T {
    default {
        type Owned = Self;
        fn into_owned(self) -> Self { self }
    }
}

impl<T> IntoOwned for &'_ T
where T: Clone + IntoOwned,
{
    type Owned = T::Owned;
    fn into_owned(self) -> Self::Owned { (*self).clone().into_owned() }
}

impl<T> IntoOwned for Cow<'_, T>
where
    T: ToOwned,
    T::Owned: IntoOwned,
{
    type Owned = T::Owned::Owned;
    fn into_owned(self) -> Self::Owned { self.into_owned().into_owned() }
}
1 Like

Not to say that I like the Owned proposal (especially the Deref part), but with your IntoOwned<T> you can't have these two implementations at the same time:

impl<T: Borrow<T>> IntoOwned<T> for T {}
impl<T: ToOwned> IntoOwned<<T as ToOwned>::Owned> for &T {}

The problem is that nothing prevents a U: ToOwned<Owned = &'static U> from existing. The first impl with T = &'static U would implement IntoOwned<&'static U> for &'static U. The second impl with T = U would also implement IntoOwned<&'static U> for &'static U.

First of all: dereferencing.

I started here:

And further demanded:

For describing this pointer-like type, it needs to implement Deref (as otherwise it's not a pointer-like type). Note that my first attempt didn't have any supertrait at all (except Sized). It's something I came up with throughout this discussion.

That's not the reason for Deref but the reason for using an associated type instead of a type argument. Deref::Target is the borrowed type, while IntoOwned::Owned is the owned type!

I had these thoughts too. It could be a question of semantics or a formalism. Let's look at std::borrow::ToOwned. Here an owned type of some type B is a type that implements Borrow<B>. It's a particular type, i.e. each borrowed type has only one (canonical) owned type.

I copied this exact concept when I demand Owned: Borrow<<Self as Deref>::Target>. That is the formal part.

The semantic is part is which type to use as the canonical owned type. It could be String for <&'a str as ToOwned>::Owned. But it could also be WeirdString or OtherString, or I guess even Cow<'a, str>. Why is it String and not WeirdString? Because String is what str considers its canonical owned type. And String certainly is a better choice than Cow<'a, str>, for example, as the latter would have unnecessary runtime cost (edit: plus the annoying lifetime, but that could be fixed if it was Cow<'static, str>, which still comes with the runtime overhead though).

But one could argue that <&'a [i32] as ToOwned>::Owned could be either Vec<i32> or Box<[i32]>. But it is the first and not the latter. std made that decision:

fn main() {
    let array = [1, 2, 3];
    let slice: &[i32] = &array;
    // We can do:
    let _: Vec<i32> = slice.to_owned();
    // But this doesn't work:
    // let _: Box<[i32]> = slice.to_owned();
    // We have to do:
    let _: Box<[i32]> = slice.to_owned().into_boxed_slice();
}

(Playground)

It seems like nobody does :slightly_frowning_face:, so you're probably in good company :stuck_out_tongue_winking_eye:.

But if there's anyone who can follow my reasoning in this post above, I'd enjoy to hear some positive feedback too (or some constructive criticism in regard to where I made a mistake or a bad choice).

I think my idea is prone to look useless / stupid at first sight but after the changes I feel more confident about it. I also believe even more than before that this is something that should be added to std some day (most likely to std::borrow because like Cow and ToOwned, it's inherently related to Borrow). Cow has some extra feature (edit: with a runtime penalty) which isn't always needed (just like a Vec<T> has some extra features compared to an Box<[T]>, but std provides both).

Either way, the whole topic of Deref, Borrow, AsRef, ToOwned, etc. is very difficult to grasp.


Note that Cow is also Deref (implementation in std).

I think my main point of disagreement is that you should choose either to accept arbitrary T or to generalize pointer types.

The main reason you give for Owned is

so the “correct” conclusion (in a type theoretical way) is not to say “I need a version of T which is Deref,” but rather “the Deref requirement is too strict for the types I want to accept.” That's why I posit that IntoOwned actually wants specialization groups, rather than an Owned wrapper. (Linked code does not include a way to access the unowned reference, but that's easy enough to add. More problematic is that the compiler can't fully resolve the involved specialization yet.)

Additionally, if you're using ToOwned as the arbiter of what the owned type is, then you probably shouldn't be providing IntoOwned for types which aren't ToOwned anyway, because std could add new ToOwned implementations to std Sized + !Clone types if so desired, changing what the correct owned type should be.

Also throwing a big wrench in your definition of IntoOwned is that &T: ToOwned<Owned=&T>. Per ToOwned, &T is an owned type. It's just that to call that implementation you need to pass &&T to to_owned or have T: !ToOwned, as otherwise T: ToOwned will be selected.

Correct. Owned<T> is a smart pointer that you can construct if you have an owned type. The owned type is T here (not Owned<T>).

I don't understand. Can you elaborate this further?

:thinking: Maybe specialization would make Owned useless. But specialization might come with some other pitfalls. However, Rust doesn't have specialization as of now. I looked at the whole issue with today's Rust and today's std, and what could be adjusted/added in std while leaving Rust as it is.

But this might be a good argument to not add it to std without first understanding the implications of specialization on that matter. Maybe there would be a solution that turns Owned indeed useless. I have the feeling that it doesn't but this isn't well-substantiated (yet).

I neither use ToOwned in Owned nor in IntoOwned's definition, only in in two IntoOwned's implementations: &'a T and Cow<'a, U>. The ToOwned bound for Cow originates in std. The bound on the reference is needed because it's the way to go from a reference to an owned value. So I'm not sure what you mean.

I don't see the problem (yet). &T: ToOwned<Owned = &T> because &T: Clone. Any type that can be cloned is ToOwned (also a reference), but what are the implications for Owned or IntoOwned?

<&T as IntoOwned>::Owned should not be &T because we don't treat &T as the owned value here but as a pointer-like type to an owned value:

Thus:

  • <&T as ToOwned>::Owned = &T
  • <&T as IntoOwned>::Owned = T (which requires a bound T: ToOwned)

Update:

To clarify:

  • <&T as ToOwned>::Owned = &T (here .to_owned() goes from &&T to &T)
  • <&T as IntoOwned>::Owned = T (here .into_owned() goes from &T to T, which requires the ToOwned bound)

A crazy hypothesis:

std::borrow::ToOwned could be entirely replaced with IntoOwned if we replace bounds like

  • X: ToOwned<Owned = O>

with

  • for<'a> &'a X: IntoOwned<Owned = O>.

Not sure about that one though. :sweat_smile:

Thus (if that was true), std wouldn't need ToOwned but only IntoOwned.


Update:

I guess in practice this wouldn't work (edit: in all cases) until issue #20671 was fixed.


Update #2:

Let's try:

use std::borrow::Borrow;
use std::ops::Deref;

pub trait IntoOwned: Sized + Deref {
    type Owned: Borrow<<Self as Deref>::Target>;
    fn into_owned(self) -> Self::Owned;
}

impl<'a, T> IntoOwned for &'a T
where
    T: ?Sized + ToOwned,
{
    type Owned = <T as ToOwned>::Owned;
    fn into_owned(self) -> Self::Owned {
        self.to_owned()
    }
}

fn classic_own<B>(b: &B) -> <B as ToOwned>::Owned
where
    B: ?Sized + ToOwned,
{
    b.to_owned()
}

fn crazy_own<B>(b: &B) -> <&B as IntoOwned>::Owned
where
    B: ?Sized,
    for<'a> &'a B: IntoOwned,
{
    b.into_owned()
}

fn main() {
    let some_slice: &[i32] = &[1, 2, 3] as &[i32];
    let owned: Vec<i32> = some_slice.to_owned();
    let classic: Vec<i32> = classic_own(some_slice);
    assert_eq!(owned, classic);
    let crazy: Vec<i32> = crazy_own(some_slice);
    assert_eq!(owned, crazy);
}

(Playground)


Update #3:

The problem with std::borrow::ToOwned is that while it may go from &T to T (where T: Clone), it cannot go from SomeSmartPointer<T> (that is Clone) to T to an owned type without doing an a potentially unnecessary clone. In that sense IntoOwned lifts ToOwned from working on ordinary references to working more generically on pointer-like types (including smart pointers).


Update #4:

Of course, this is related to specialization.

I don't think so because of this:

Deref is (arguably) what makes a smart pointer a smart pointer pointer-like type.


Hmmmm… :thinking: Perhaps you conviced me. We could do this:

pub trait IntoOwned: Sized + Borrow<Self::Borrowed> {
    type Owned: Borrow<Self::Borrowed>;
    type Borrowed: ?Sized;
    fn into_owned(self) -> Self::Owned;
}

(Playground)

Update:

Tried to modify deref_owned accordingly, but ran into problems:

impl<T> IntoOwned for Vec<T> {
    type Owned = Self;
    type Borrowed = ???;
    fn into_owned(self) -> Self::Owned {
        self
    }
}

I think it must be Deref and that also fits the goals of my proposal and what I wrote here:

Another Update:

Sorry for all the updates. :upside_down_face:

Clarifying: the following describe separate concepts, ordered from strictest to most general:

  • A pointer-like type that can be converted into an owning pointer-like type to the same pointee type.
  • A pointer-like type that can be converted into an owned type that can be used by-ref like the pointee type.
  • T, or some other (potentially pointer-like) type which can both be used like T by-ref and has a (optional: projective) conversion into T by-value.
  • T, or some other (potentially pointer-like) type which can both be used like T by-ref and has a (optional: projective) conversion into some owning (potentially pointer-like) type which can be used like T by-ref.

The concept of “owning type” is deliberately left undefined in the above. (For good reason: &T is both an “owning type” of &T and a “borrowing type” of T. Rust isn't C++ where T& is not a normal type and you have to use std::reference_wrapper<T> to turn it into a real type which can be owned.)

Defining these in a C++20 concepts like manner of “what can I do with a conforming value” rather than the stricter language of Rust traits I expect can be illuminating.

... In fact, I suspect that what you want is very similar to C++ std::forward<T>. (Not an rvalue reference but rather a forwarding reference.) Of course Rust types are not address-sensitive, so using C++ terms isn't perfect. (Notably, the closest relative to T&&C++ is &move TRust. If T&& is an rvalue reference, this is mostly the same (modulo destructive move semantics), but when T&& is used as a forwarding reference it is much closer to just TRust; the point of a forwarding reference is that it can be an lvalue or an rvalue reference, both of which are just normal types in Rust. And C++ values just can't be used by-value in the Rust terminology.)

Your Owned type is a pointer-like type that wraps some T in order to use the second concept/abstraction as if it were the fourth. (The first is the class that Box/Vec/String are in.)

(It is at this point I feel obligated to mention that I am working on the “Storage API” and receiving a Rust Foundation grant. The Storage API in full generality in fact allows writing an Owned-like type as Box<T, InlineStorage<{Layout::new::<T>()}>. The one difference is that this is by your definition a “smart pointers which [is] already owned and where you can borrow their pointee” and not “a smart pointer that you can construct if you have an owned type.”)


It's quite simple? Use <Self as Deref>::Target, here [T]: [playground] It's

impl<T> IntoOwned for Vec<T> {
    type Owned = Vec<T>;
    type Borrowed = [T];
    fn into_owned(self) -> Self::Owned {
        self
    }
}

// let owned: Vec<_>;
let pre_addr = owned.as_ptr() as usize;
let owned = owned.into_owned();
let post_addr = owned.as_ptr() as usize;
assert_eq!(pre_addr, post_addr);

It seems you're focused on Deref for the ergonomics of deref coercion and not the actual abstraction vocabulary you want, which is I argue some Self which “can be used by-ref as T” (Borrow<T>, not Deref<Target=T>), “can be converted by-value into some value which can be used by-ref as T”, and “projective onto a single T which can be derived from Self”.

This is exactly

Unfortunately, this is still impossible to implement for arbitrary T due exclusively to the requirement to be projective onto the (have a single associated) owned type.

If IntoOwned is defined non-projectively, however, in theory this is resolvable, with T: IntoOwned<T> and &T: IntoOwned<<T as ToOwned>::Owned> able to coexist, iff the compiler can be informed that <T as ToOwned>::Owned and &T are disjoint... but I AIUI this does not hold.

As such, for such an implementation to exist, one of these implementations (probably the ToOwned bounded one!) will have to specialize the other. In the in-between time until the compiler can be convinced these are disjoint/specializing implementations, using an Owned wrapper to force them to be disjoint (manually select a specialization) is reasonable, but not really a fit design for std.

And if you're using an Owned wrapper to avoid the need for specializations for IntoOwned for &T, then AIUI all implementations become projective again, and using the associated type comes with purely benefits.


I know this post is a bit long, responding to the series of incremental updates. Please remember to consider the first section about principles and not just the second section recommending potential solutions :slightly_smiling_face:

1 Like

It's worth noting that the standard pattern for Path (which works equally well for str, [T], CStr, OsStr) is AsRef<Path> + Into<PathBuf>. However, this loses the blanket impl provided by Borrow, and Into may not always be available.

While designing IntoOwned, it should ideally be kept in mind that Self: IntoOwned is fundamentally an optimization and generalization over Self: Borrow<T>, T: ToOwned. Fully excluding any types in that class should be done deliberately because they lack some specific property you're looking for, or because of a limitation of the type system which excludes implementations due to improper specialization (stable: any).

Working around type system limitations is fine (moreso for 3rd party than std APIs), but again should not come at the cost of excluding types accepted by the less optimized API. (Merely lacking a semantically fine impl is acceptable, as it can be provided by an adapter (e.g. Owned<T>).)

I don't understand everything you wrote (yet?). But if I understand you right, then you acknowledge that Owned is a necessary workaround as of today's Rust but could be made superfluous if one day we could implement IntoOwned<T> for T while also implementing IntoOwned<<T as ToOwned>::Owned> for &T?

How would that translate to my example here?

Would this be just:

trait Parse<T: ?Sized> {
    type Pointer<'a>: IntoOwned<<Self as ToOwned>::Owned> + Borrow<Self> + Debug
    where
        Self: 'a;
    fn parse(&self) -> Option<Self::Pointer<'_>>;
}

?

I guess that could work (but breaks deref). Now you could say:

Why do I want deref coercion? Because if I work solely with references, deref works too! If I work with Cow, then deref works also. If I always return an owned value (without wrapper), then deref doesn't work but I don't need it either. So yes, this is about ergonomics! :smile:

Following your proposal, I don't always return an owned value, a smart-pointer, or a reference (for each of those three, ergonomics would be nice). Instead I return an unhandy "thing", which requires .borrow() or .into_owned() to be used.

I feel like the abstraction you made doesn't cover &'a T correctly (which is Deref). I.e. when I can't use &'a T but have to use that "thing" (sorry for the terminology, I have no better word for it), then I lose ergonomics. Thus the "thing" isn't a proper generalization of &'a T.

Maybe that can be solved somehow though?

Maybe it is because std lacks IntoOwned? :see_no_evil:

I see what you mean:

  • optimization because it can avoid an unnecessary clone (i.e. if we would just set T = Self)
  • generalization because IntoOwned doesn't require a type argument T

You mean that IntoOwned should automatically be implemented for i32 or any other "plain owned type"?

Even if that was possible, I wonder if there's a solution for ergonomics:

[…] if I work solely with references, deref works too! If I work with Cow, then deref works also. If I always return an owned value (without wrapper), then deref doesn't work but I don't need it either.

Following your proposal, [...] I return an unhandy "thing", which requires .borrow() or .into_owned() to be used.

Don't get me wrong, I think it would be great if:

  • IntoOwned could be implemented for any "owned" T (without the Owned wrapper).
  • Ergnomics of my example here are not impaired.

You could say Owned isn't very ergonomic either, but I'd like to point out that having to use Owned in that example is limited to the trait implementation and doesn't need to be known by its users or be reflected in the interface somehow (except Deref).


Update:

Note that while Owned is needed in case of the GAT, it's not needed in the following example anymore:

In the above example, Owned can be omitted, i.e.:

generic_fn("Echo".to_string());

works just fine.

(Edit: This doesn't work anymore in the recent version 0.4.0 of deref_owned, see test source, where the Owned wrapper is needed again, and the following post for a motivation.)

(Test case in source code of deref_owned)

I really only need Owned in case of the GAT, where I feel the terminology "smart pointer to its owned value" would be fitting:

Trying to understand this now. I assume that "by-ref" you mean either .as_ref(), .deref(), or .borrow() without specifying it.

use std::borrow::Borrow;
use std::ops::Deref;

fn main() {
    let s: String = "".to_string();
    let _: &str = s.as_ref();
    let _: &str = s.deref();
    let _: &str = s.borrow();
}

(Playground)

All three work. (It's a bit confusing that .as_ref() can do the same as .deref() :sweat_smile:.)

I would agree.

I also agree.

Hmmm… :thinking: by definition, I said IntoOwned was a pointer-like type. This rules out the third and fourth concept:

Maybe I should have named it PointerIntoOwned, which I did in one of my earlier approaches, instead of IntoOwned. The name "IntoOwned" is misleading: it's not an arbitrary type that can be converted into an "owned" type (whatever that is), but it is

  • a pointer-like type, which
  • can be converted into an "owned" type (IntoOwned::Owned), that
    • can be used "by-ref" (through .borrow()) as the pointed-to type.

So IntoOwned isn't a general conversion into an owned type but a bit more specific.

Speaking of naming …

… if Owned is not an "owned" type but a smart pointer that owns its pointee, perhaps it should be better named Owning instead of Owned?

But back to this:

Not sure why you think I use the fourth concept. Maybe because of the following implementations?

impl<T: ?Sized> IntoOwned for Box<T> {
    type Owned = Self;
    fn into_owned(self) -> Self::Owned {
        self
    }
}

impl<T> IntoOwned for Vec<T> {
    type Owned = Self;
    fn into_owned(self) -> Self::Owned {
        self
    }
}

impl IntoOwned for String {
    type Owned = Self;
    fn into_owned(self) -> Self::Owned {
        self
    }
}

(source)

This looks a bit like IntoOwned supports .into_owned() for some types but not for others. But why is that? It's because IntoOwned actually is more like PointerLikeTypeThatCanBeConvertedIntoAnOwnedTypeFromWhichYouCanBorrowTheOriginalPointee. And this shouldn't (and can't) be implemented by i32, for example.

I think that:

  • IntoOwned as defined in version 0.3.0 of deref_owned is a generalization of std::borrow::ToOwned (as suggested in this post); i.e. if we had IntoOwned we wouldn't need ToOwned (given issue #20671 was fixed and assuming we'd be happy with the different syntax when using the trait).
  • A "smart pointer which owns its target" (whether we call it Owned or Owning) is necessary if we want to return a pointer-like type to a value where sometimes the value is owned and sometimes it's not, and where this is determined at compile-time through a GAT. (For the run-time case, we already have Cow, which works fine.)

Maybe it's possible to find an even more general version of IntoOwned like you suggested (maybe if Rust's type system is more advanced in future), and that might be a good reason to not add such a trait to std now.

One thing that I don't like about my version of IntoOwned is that apparently all smart pointers have to implement it (in addition to Deref), and most often that implementation is trivial:

impl<T> IntoOwned for SomeSmartPointer<T> {
    type Owned = Self;
    fn into_owned(self) -> Self::Owned {
        self
    }
}

I try to understand better how &'a T, Cow<'a, T>, and Owned<T> seem to be the only examples that have different implementations. This makes me suspect that something might be still wrong.

&'a T and Cow<'a, T> are having a lifetime, so that justifies a different implementation (to get rid of it during the process). But what about Owned<T>? We might try to write:

impl<T> IntoOwned for Owned<T> {
    type Owned = Self;
    fn into_owned(self) -> Self::Owned {
        self
    }
}

I.e. why is Owned<T> not converted to Owned<T> when going through .into_owned()? I get this interesting error message when I try:

error[E0277]: the trait bound `T: Clone` is not satisfied
   --> src/lib.rs:119:18
    |
119 |     type Owned = Self;
    |                  ^^^^ the trait `Clone` is not implemented for `T`
    |
    = note: required because of the requirements on the impl of `ToOwned` for `T`
note: required because of the requirements on the impl of `Borrow<T>` for `Owned<T>`
   --> src/lib.rs:59:9
    |
59  | impl<B> Borrow<B> for Owned<<B as ToOwned>::Owned>
    |         ^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: required by a bound in `IntoOwned::Owned`
   --> src/lib.rs:93:17
    |
93  |     type Owned: Borrow<<Self as Deref>::Target>;
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `IntoOwned::Owned`
help: consider restricting type parameter `T`
    |
118 | impl<T: std::clone::Clone> IntoOwned for Owned<T> {
    |       +++++++++++++++++++

But we can fix that with:

impl<B> Borrow<B> for Owned<B> {
    fn borrow(&self) -> &B {
        &self.0
    }
}

impl<B> BorrowMut<B> for Owned<B> {
    fn borrow_mut(&mut self) -> &mut B {
        &mut self.0
    }
}

Now these implementations are all the same:

impl<T> IntoOwned for Owned<T> {
    type Owned = Self;
    fn into_owned(self) -> Self::Owned {
        self
    }
}

impl<T: ?Sized> IntoOwned for Box<T> {
    /* … same here … */
}

impl<T> IntoOwned for Vec<T> {
    /* … same here … */
}

impl IntoOwned for String {
    /* … same here … */
}

(and we could add even more for Rc, Arc, etc.)

But now IntoOwned won't allow me to go from Owned<i32> to i32 anymore. With &'a T and Cow<'a, T> everything worked fine though. So this isn't really an improvement.

Maybe the correct way would be to simply remove the implementations of IntoOwned for Box<T>, Vec<T>, String, etc. Where needed, a smart pointer to the value pointed-to by an owned inner value (:face_with_spiral_eyes:) could be used. This is what I previously did in mmtkvdb when I wanted to return a re-aligned array of i32's for example.

Perhaps this change would make things a bit less messy or a bit less arbitary. IntoOwned would then only be implemented for &'a T, Cow<'a, T>, and Owned<T>. I'll look into that.


Update:

Maybe the correct way would be to simply remove the implementations of IntoOwned for Box<T>, Vec<T>, String, etc.

Done in deref_owned version 0.4.0.

And if you're working with Borrow<T> (i.e. the standard trait for a type which can be used as-ref like T[1]), you don't have deref coersion.

Either you call borrow early on and use the borrowed version, or you could (internally only) use a

struct LetMeDerefBorrowPlz<T>(T);
impl<T: Borrow<U>, U> Deref for T {
    type Target = U;
    fn deref(&self) -> &U { self.borrrow() }
}

(EDIT: I didn't test this. Looking at it a bit later: this won't tyck as is (uncovered U). :frowning_face:)

However, I do agree that it would be nice to have some sort of MethodDispatchAs<T> trait which covers all types which have method dispatch to T via auto(de)ref, in addition to just Deref, which excludes T itself.

Using impl IntoOwned as a return type (e.g. trait Parse) though seems odd. Unless generic users of Parse need to .into_owned(), the return type only needs to be bound on Borrow. All parser combinators I can think of are happy to deal exclusively in &[_], and e.g. trying to return Strings from a list combinator is actively a bad thing. The concrete instantiation knows if the given type is e.g. String or &str.

I wonder if what what you really want is a self-referential kind of thing, e.g. to yoke a borrowed output to an owned input.

Obviously with just a trait definition and not a set of expected uses it's not really possible to suggest an alternative; you could be relying on arbitrary details.

Because that example only uses &str and String. If you were to want to use e.g. i32, you would still have to call it as generic_fn(Owned(0)).

If Owned were just an implementation detail, I'd be less concerned about its use.

IntoOwned may represent the second, but the point of Owned is to lift an arbitrary T into a pointer-like-to-T. With Owned in the arsenal, you can call the second concept as if it were the fourth, by wrapping a by-value in Owned.

But you're fine not removing a Box, so what's different about Owned? (Legitimate question, not a leading one.)


This is very clearly not on topic for irlo anymore, though. Feel free to @ me on urlo with some links to you actual proper use case using IntoOwned in its definition and I'll see if I can't diagnose some incidental complexity you've overlooked as inherent. Having the actual use case in front of me will also make it easier to communicate :slightly_smiling_face:


One bit of generic generic advice: you only should be adding bounds if the bounds are consumed by generic users. Even if e.g. every reasonable output type implements, say, Debug, you don't bound the associated type on Debug. Instead, the concrete instantiation sees that the type is Debug and can use that impl. The same goes for any functionality so long as the type is not opaque (i.e. impl Trait).


  1. Providing fn(&self) -> &T with the guarantee that &Self and &T behave “the same.” ↩︎

Not sure if it's so clear. Depending on how specialization turns out, Owned might still be a case for std::borrow. Anyway, I shifted this discussion to URLO.

I would like to thank particularly @CAD97, @conradludgate, and @SkiFire13 for their input. :heart:

I think I gained a better understanding of the whole issue throughout this discussion. :smiley:

For those who are interested in my conclusion in this matter, you may take a look at the solution of the URLO thread that was created out of this one.

One case:

fn generic_fn(arg: impl GenericCow<Borrowed = str>) {
    let reference: &str = &*arg; // or: arg.borrow()
    assert_eq!(reference, "Hello");
    let owned: String = arg.into_owned();
    assert_eq!(owned, "Hello".to_string());
}

(source of test)

Here GenericCow::into_owned will not perform an unnecessary clone if it's known at compile time that the function is called with an Owned value. Note that .into_owned() might be in a branch that's not always executed (the typical copy-on-write scenario).

The proposed wrapper (Owned<B>) is no longer owning its deref target but owns a value of type <B as ToOwned>::Owned and uses the same semantics as Cow::<'_, B>::Owned to provide a Deref<Target = B> implementation (see source in std and compare with source of deref_owned::Owned::deref implementation).